A binary search or half-interval search aims to find the element in a sorted array by first comparing target element with middle element to see whether the element is in first half or second half and keep repeating this until it finds the target element.
- Find middle element in sorted array: (first+last)/2
- If x matches with middle element, we return the mid index.
- Else If x is greater than the mid element, then x can only lie in right half subarray after the mid element. So we recur for right half.
- Else (x is smaller) recur for the left half.
[1,3,12,23,34,56,62,98,99]
x = 12
Iteration 1:
1. mid = 1+9/2 = 5
2. x<mid
3. recur in left half
Iteration 2:
1. mid = 1+5/2 = 3
2. x==mid
3. return mid
Element is at position 3
Worst-case complexity: o(logn) Best-case complexity: o(1)