Data Structures and Algorithms

Card Set Information

Author:
rishabh9
ID:
213329
Filename:
Data Structures and Algorithms
Updated:
2013-04-14 05:07:31
Tags:
data structures algorithms
Folders:

Description:
Personal Notes on Data Structures and Algorithms. (Hope it helps others too)
Show Answers:

Home > Flashcards > Print Preview

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


  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.

What would you like to do?

Home > Flashcards > Print Preview