Why Binary Search?

Binary search is widely used in finding elements in a sorted array/matrix. The concept of binary search is not hard to understand. When searching for an element in a sorted array, we compare the middle element with the target, if the middle element is greater than the target, meaning the target may appear in the first half of the array. If not, then the target may appear in the second half of the array. The following is a basic chunk of code when finding an element in a sorted array.

#Given a sorted array and a target element, return the index of target if found, return -1 if not found
def binary_search(array, target)
    start_index = 0
    last_index = array.size - 1
    while start_index + 1 < last_index do 
        mid = start_index + (last_index - start_index) / 2
        if array[mid] < target            
            start_index = mid        
        else
            last_index = mid
        end
    end
    return start_index if array[start_index] == target
    return last_index if array[last_index] == target
    return -1
end

When searching for the target, we compare the middle element with the target, then we decide whether to go left or right. The key to binary search is that it only goes through half of the array in each loop. Compearing with liner search, It has great logarithmic time complexity even dealing with the worst case.

Running time analyze

Why do we say the binary search is having logarithmic time complexity? Let’s calculate it together by going through the previous code with a simple example.

We have a sorted array: [1, 2, 3, 4, 5, 6, 7, 8], we wanna search for element 7 and return its index. The following graph will help to understand the process:

Illustration of binary search

As we can see, each time we enter the loop, binary search will cut off half of the array. The overall running time could be represented as T(n) = T(n/2) + O(1) . Here T(n) represents the running time of the process when the input size is n, and O(1) time represents the constant operations include: 1). calculate mid index; 2). compare array[mid] and target value; 3). re-assign start or last with mid value. If we expand this equation, we’ll get:

T(n) = T(n/2) + O(1)
     = T(n/4) + O(1) + O(1)
     = T(n/8) + O(1) + O(1) + O(1)
     = ....
     = T(n/2^k) + k * O(1)
     = ....
     = T(1) + log₂n * O(1)

Since each layer’s calculation will cut-off half of the array size, and there are total log₂n layers to get the size n array to size 1 array . So the time complexity is O(log₂n) for binary search.

Exercise

Let’s implement binary search together on some classical problems together to better understand this algorithm.

Sqrt(x)

Binary search is mainly used in searching, it’s also helpful in doing calculations. For example, the following problem is asking the square root of an input integer.

Sqrt(x) - LeetCode

Since the square root of an integer must be less than or equal to itself. Thus we have the answer in the range of [0, x]. We could have our start number as 0, and last number as x, then using the middlebetween these two to make the decision to move left or right.

def sqrt(x)
    start = 0
    last = x
    while start + 1 < last do 
        mid = start + (last - start) / 2
        if mid * mid < x
            start = mid
        else
            last = mid
        end
    end
    return start if start * start == x
    return last if last * last == x
    return start
end

Find peak element

Another example is that the binary search can find the maximum element in an array that is not sorted but has some path to find.

For example, the following problem needs to return the peak element in a mountain array. A mountain array must have a peak element which is the maximum value, remaining elements are less than the peak value. The left side elements are in ascending order, the right side elements are in descending order.

Find Peak Element - LeetCode

You may think to iterate this array once to find the peak value which has a liner running time. However, that’s not the best solution. Binary search can help to save some running time.

Let’s draw this array out, and we have 3 stages here: uphill, peak, downhill.

         * <= peak          
        / \
      |/   \|
 a => |     | <= b
     /|     |\
    /         \
   /           \
*If middle falls at peak: return middle index;
*If middle falls at point a: the peak will only occurs at its right side, we move start to middle;
*If middle falls at point b: the peak will only occurs at its left side, we move last to middle;

We need to consider three cases when the middle element falls into any of these stages:

• If the middle element anciently is the peak, meaning that array[middle — 1] < array[middle] > array[middle + 1] , we simply return middle;
• If the middle is on the uphill stage, which is array[middle — 1] < array[middle] < array[middle + 1] , meaning that the peak will not occur on the left side of the middle element, we move start to middle ;
• If the middle is on the downhill stage, which is array[middle — 1] > array[middle] > array[middle + 1] , meaning that the peak will not occur on the right side of the middle element, we move last to middle .

After figuring out the conditions, the code is not hard to implement:

def find_peak_element(nums)
    start = 0
    last = nums.size - 1
    while start + 1 < last do 
        mid = start + (last - start) / 2
        if nums[mid] > nums [mid - 1] && nums[mid] > nums [mid + 1]
            return mid
        elsif nums[mid] > nums [mid - 1] && nums[mid] < nums [mid+1]
            start = mid
        else
            last = mid
        end
    end
    
    if nums[start] > nums[last]
        return start
    end
    return last
end

Hope my post can help you understand the binary search algorithm!