Binary Search

I already cover some sorting algorithms here. Now, it's time to find an element within.

It is easy to find an element within a sorted list. If not, we need to check every element. Binary Search is a search algorithm within a sorted list. Here is how it works:

  1. Select an element in the middle.
  2. Check, whether it is lower or higher than the target.
  3. Narrow the portion to the right half if the middle is lower than the target.
  4. Otherwise, narrow it to the left half.
  5. Do it again repeatedly until the target is found.

This picture could help you to visualize the Binary Search.

Binary Search

An example in C.

int binary_search(int *list, int left, int right, int target) {
    if (right >= left) {
        int middle = left + (right - left) / 2;
    
        if (list[middle] == target) return middle;
    
        if (list[middle] < target) {
            return binary_search(list, middle + 1, right, target);
        }
    
        return binary_search(list, left, middle - 1, target);
    }
    
    return -1;
}

The time complexity of Binary Search is O(log n). This algorithm is quite famous. It is also often asked in a programming interview.

Related Articles