Binary Search Algorithm

1. Place the problem

Given an array of n-element integers, sorted, find the position of any value in the array

For example, for a 10-element integer array between -20 and 20, find the position of the value 5

There are two ways to handle this problem: linear search and binary search

• Linear search will loop through each element in the array until it finds a value, the time complexity is O (n).
• Binary search has time complexity O (log (2) n) => This way is more optimal, faster.

2. How does Binary search work?

• Let L be the first value of the array, R is the last value of the array, M is the value at the center of L and R.

• We see M (1) <target (5) so the target is between 1 and 17, continue to set L and M to new position

• the target is now in the range 2-9, we move R to a new location

• So we have found the target after 3 steps, if using linear it takes 7 steps
• If the target doesn’t exist in the array, it takes 3 steps to search while linear takes 10 steps to find the last position of the array.

3. Time Complexity

• We see that the number of search elements changes by 10 -> 5 -> 2
• If initially there are n elements, the number of elements changed will have the following generalized form

• It takes about x + 1 = log (2) n + 1 ≈ log (2) n steps to find the target. If the array has 10,000,000 elements, it only takes about 24 steps to find the target. Whoa !!!!

4. Demo (Ruby language)