Home > Flashcards > Print Preview
The flashcards below were created by user
rishabh9
on FreezingBlue Flashcards. What would you like to do?

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
 Recalculate mid = (low + high) / 2
 Repeat, till item is found atÂ a[mid]. Return mid
 If item is not found, return null.

