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

Com­plete Code:

Output:

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

You may also like...

• Vince Lieu

if (mid>key)
do recur­sive search on the left half of the array.

else
do recur­sive search on the right half of the array.