Data Structures and Algorithms

  1. What is the prerequisite for Binary Search?
    The input list/array of items need to be sorted.
  2. Time complexity for Binary Search
    • O(log n)
    • Because we only search for one half in every iteration.
  3. 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.
Card Set
Data Structures and Algorithms
Personal Notes on Data Structures and Algorithms. (Hope it helps others too)