Binary search

• The input must be a sorted list of elements.

• Given you need to search on an array or set, it is better to start the search in the exact middle of this array or set.

• That aids in velocity because at each pass you use that logic on the remaining elements you eliminate half of the elements.

• LOGARITHMIC TIME: For a list of n elements, it will take log2 n steps on the worst scenario.

  • O(log ) n

• LINEAR TIME: For a list of n elements, when you go through all the list from the 1st element to the last - it will take n steps on the worst scenario.

  • O(n)

Logarithms

• They are the flip of exponentials.

(when not specified, the default base is “2”)

  2			      |-----------> argument
10  = 100 	== 	log  100 = 2 -----> logarithm
                           10  -----------> base
 3
2  = 8         == 	log 8 = 3
                           2

 4
2  = 16        == 	log 16 = 4
                           2

 5
2  = 32        == 	log 32 = 5
                           2