-
What is the prerequisite for Binary Search?
The input list/array of items need to be sorted.
-
Time complexity for Binary Search
- O(log n)
- Because we only search for one half in every iteration.
-
Algorithm (or idea behind) Binary Search
- Need sorted input (say, in an array in ascending order), and item.
- Pointers to low and high
- Pointer mid, such that mid = (low + high) / 2
- if item = a[mid], return mid
- Else check if item is greater than a[mid]
- If yes, then your low = mid + 1
- If item is less than a[mid] then, high = mid - 1
- Re-calculate mid = (low + high) / 2
- Repeat, till item is found at a[mid]. Return mid
- If item is not found, return null.
|
|
