Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Pinterest
Share On Reddit
Share On Stumbleupon
Contact us
Hide Buttons

Binary Search

Objec­tive : Write an algo­rithm to find an ele­ment in an sorted array

Input: A sorted array, arrA[] and an key

Out­put : Return true if ele­ment is found, else false.

Approach: The idea is to com­pare the mid­dle ele­ment of array with the key, if key equal to the mid­dle ele­ment , that’s it you have find your ele­ment, return true. If key is greater than the mid­dle ele­ment, chuck out the first half of the array, you wont find your key in the first half and do the recur­sive search on the right half of the array and vice versa.

If(mid_element==key)
return true;
else if (mid>key)
do recursive search on the right half of the array.

else
do recursive search on the left half of the array.

Time Com­plex­ity: O(logN) –since we are elim­i­nat­ing half of the array with every comparison.

Binary Search

Binary Search

Com­plete Code:


Output:

The 99 present in array a ??? :true
The 76 present in array a ??? :false

 

You may also like...