Binary searching

Binary search is an efficient technique applied on sorted list. It works only on sorted list. In this technique, the key element is compared with the middle element. If it matched, it returns SUCCESS ,else it checks whether the key element is greater or lesser than the middle element . The searching part moves to the second half of the array when the key element is greater than the middle element or it moves to the first half .The process continues until it matches or there are no further elements to compare.

Recursive Algorithm

binary_search(a,low,high){

mid=(low+high)/2

if(a[mid]==key)

return success

else if(a[mid]<key)

low=mid+1;

else

high=mid-1;

binary_search(a,low,high)

}

Now, let us see an example

An array having sorted list elements 1, 5, 7, 8, 13, 19, 20, 23, 29. The key element is 23.When it is compared with middle element, key is greater so it moved to second half. It recursively applied until it found.

The element is found at 7th position in the array.

Let us see the code for the binary searching technique

Program in C language:

Program in JAVA language:

Program in php:

Lets move to the time complexities of the binary search .

Best case : O(1)

Worst case : O(logn)

Average case : O(logn)

With this we will end this story by explaining binary search, algorithm, programs and time complexities.