Home arrow JavaScript arrow Page 5 - Binary Searching
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
Rating: 5 stars5 stars5 stars5 stars5 stars / 3
June 30, 2008
TABLE OF CONTENTS:
  1. · Binary Searching
  2. · Tutorial Approach
  3. · Demonstration of Binary Search
  4. · Demonstration continued
  5. · Algorithm for Binary Search

print this article
SEARCH DEVARTICLES

TOOLS YOU CAN USE

advertisement
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.

blog comments powered by Disqus
JAVASCRIPT ARTICLES

- More Top jQuery Tutorials for Beginners
- More Top jQuery Plugins for Menus
- Top jQuery Tutorials for Beginners
- New UI Framework and SDK for JavaScript Rele...
- JavaScript OpenPGP Tool, Node.js 0.6.3 Avail...
- Yahoo Releases Cocktails Language and Develo...
- Customizing jQuery Slideshows: Dynamic Contr...
- Customizing jQuery Slideshows: the animate()...
- Customizing jQuery Slideshows: slideUp() and...
- Customizing jQuery Slideshows: hide() and sh...
- Web Workers: Performing Calculations in Para...
- More Top JavaScript Frameworks and Libraries
- More Dynamic jQuery Styling Techniques
- The Top JavaScript Libraries
- The Top JavaScript Frameworks

Dev Articles Forums 
 RSS  Articles
 RSS  Forums
 RSS  All Feeds
Weekly Newsletter
 
Developer Updates  
Free Website Content 
Contact Us 
Site Map 
Privacy Policy 
Support 



© 2003-2012 by Developer Shed. All rights reserved. DS Cluster 2 - Follow our Sitemap
Popular Web Development Topics
All Web Development Tutorials