JAVASCRIPT

Binary Searching

Binary Searching involves searching for an element in an array, where the items are arranged in ascending or descending order. That means the entries in the array are sorted. If you want to learn how to write a function that does this, keep reading.

Author Info:

By: Chrysanthus Forcha

Poor Best

Rating:

/ 3

June 30, 2008

TABLE OF CONTENTS:

Compare the key with a middle element. If the key is equal to the middle element, return the index of that middle element.
If the key is not equal to the middle element, since the list is sorted, decide whether the key lies above or below the middle element. Ignore the section that does not have the key.
Go to the section that has the key and repeat the above two steps.
Carry on repeating the first two steps until the middle element is equal to the key.

The implementation for the binarySearch() function takes the array and the key as arguments. If the element is found, it returns the index. If the element is not found, it returns the length of the array. This is the code for the web page, which includes the binarySearch() function.

<html>

<head>

//the array which may contain the element we are looking for

theList = new Array()

theList[0] = 'E';

theList[1] = 'I';

theList[2] = 'O';

theList[3] = 'P';

theList[4] = 'Q';

theList[5] = 'R';

theList[6] = 'T';

theList[7] = 'U';

theList[8] = 'W';

theList[9] = 'Y';

function binarySearch(theList, key)

{

var left = 0;

var right = theList.length - 1;

while (left <= right)

{

var mid = parseInt((left + right)/2);

if (theList[mid] == key)

return mid;

else if (theList[mid] < key)

left = mid + 1;

else

right = mid - 1;

}

//when element is not found

return theList.length;

}

function search()

{

var elementFound = binarySearch(theList,'U');

alert(elementFound);

}

</script>

</head>

</body>

</html>

Array of Strings

An array of strings works in the same way as an array of letters as far as binary search is concerned.

You can test this by replacing the array of letters in the code with the following array of sorted strings:

theList[0] = 'boys';

theList[1] = 'camera';

theList[2] = 'can';

theList[3] = 'children';

theList[4] = 'girls';

theList[5] = 'man';

theList[6] = 'people';

theList[7] = 'pot';

theList[8] = 'umbrella';

theList[9] = 'woman';

Conclusion

You can use the ordinary search or binary search method to find an element (text) in a list. When your list is not sorted, you use the ordinary search method. The time spent searching with this method can only be small if your element is at the start or near the start of the array; you will not usually be that lucky, so your search time will usually be high. There are many sources of sorted lists. When your list is sorted, the time spent searching with binary search will always be small.

DISCLAIMER: The content provided in this article is not warranted or guaranteed by Developer Shed, Inc. The content provided is intended for entertainment and/or educational purposes in order to introduce to the reader key ideas, concepts, and/or product reviews. As such it is incumbent upon the reader to employ real-world tactics for security and implementation of best practices. We are not liable for any negative consequences that may result from implementing any information covered in our articles or tutorials. If this is a hardware review, it is not recommended to open and/or modify your hardware.