Binary Searching - Algorithm for Binary Search
(Page 5 of 5 )
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>
<script type="text/javaScript">
//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 onload="search()">
</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. |
