Binary Search (Recursive)Search(target,a,left,right) This is an O(log n) algorithm.
1. If left >= right then
1.1 If a[left] equals target then
1.1.1 return index left
1.2 Else
1.2.1 return -1 (i.e. 'not found’)
2. Set mid = (left+right)/2
3. If target is greater than a[mid] then
3.1 return Search(target,a,mid+1,right)
4. Else
4.1 return Search(target,a,left,mid)
The values to be searched must be sorted in order
Go to the mid point of the list or array
Compare this with the value to be found
If the value to be found is less than the mid point search the first half of the list or array
If the value to be found is greater than the mid point search the second half of the list or array
Divide the next part of the list or array in exactly the same way and perform the same comparisons until the item is found or no more searches can be made.