Searching for things

Suppose that you are given an unsorted pile of numbered boxes, and you are tasked with opening the box numbered 150. What is your strategy?

Binary search

Hopefully, you realise that you can search through an array faster if you have some knowledge about the array. If the array is sorted, but you have no knowledge about its distribution, then a binary search is the optimal algorithm.

Pseudocode for finding the value k in array A of size N:

i = N/2
step = N/2
while A[i] != k:
   step = step / 2
   if A[i] < k: 
      i = i + step
   else:
      i = i - step

Try using this algorithm to search for a few elements in [1, 3, 4, 6, 7, 8, 10, 13, 14].

The complexity of this algorithm is the height of a binary tree, O(log N).