Binary Search: From Basics to Medium-Difficult Problems

Binary search is one of the most fundamental algorithms in computer science. While most coders are familiar with its basic concept, many struggle to apply it to medium-difficult problems. This blog aims to bridge that gap by explaining the core concepts, providing practical examples, and sharing tips to tackle binary search problems effectively.

Binary Search: The Basics

Binary search is an efficient algorithm for finding an item from a sorted list of items. It works by repeatedly dividing the search interval in half. If the value of the search key is less than the item in the middle of the interval, narrow the interval to the lower half. Otherwise, narrow it to the upper half. Repeatedly check until the value is found or the interval is empty.

Basic Algorithm Steps:

1. Start with the entire sorted array.
2. Compare the target value with the middle element.
3. If the target value is equal to the middle element, return the index.
4. If the target value is less than the middle element, repeat the search in the left half.
5. If the target value is greater than the middle element, repeat the search in the right half.

Short Code Example:

int binarySearch(vector<int>& arr, int target) {
    int low = 0, high = arr.size() — 1;
    while (low <= high) {
        int mid = low + (high — low) / 2;
        if (arr[mid] == target) return mid;
        else if (arr[mid] < target) low = mid + 1;
        else high = mid — 1;
    }
    return -1; // Target not found
}

Lower Bound, Upper Bound, and Binary Search Built-in Functions

In C++, the STL provides built-in functions for binary search:

• lower_bound: Returns the first element that is not less than the target.
• upper_bound: Returns the first element that is greater than the target.
• binary_search: Returns true if the target exists in the array, otherwise false.

Example Code for Built-in Functions:

#include <iostream>
#include <vector>
#include <algorithm> // for lower_bound, upper_bound, binary_search

using namespace std;

int main() {
    vector<int> arr = {1, 3, 5, 7, 9, 11};
    int target = 7;

    // lower_bound: First element not less than target
    auto lb = lower_bound(arr.begin(), arr.end(), target);
    if (lb != arr.end()) {
        cout << "Lower bound of " << target << " is at index: " << (lb — arr.begin()) << endl;
    }

    // upper_bound: First element greater than target
    auto ub = upper_bound(arr.begin(), arr.end(), target);
    if (ub != arr.end()) {
        cout << "Upper bound of " << target << " is at index: " << (ub — arr.begin()) << endl;
    }

    // binary_search: Check if target exists
    if (binary_search(arr.begin(), arr.end(), target)) {
        cout << target << " exists in the array." << endl;
    } else {
        cout << target << " does not exist in the array." << endl;
    }

    return 0;
}

Output:

Lower bound of 7 is at index: 3
Upper bound of 7 is at index: 4
7 exists in the array.

Can Binary Search Be Applied to Unsorted Arrays?

No, binary search requires the array to be sorted. If the array is unsorted, you must sort it first, which takes O(n log n) time. However, there are specific problems where binary search can be applied creatively, even if the array isn't explicitly sorted.

Problem: Finding the Last Positive Number in a Array

Given an array of length n, where the first i elements are positive (including 0) and the remaining elements are negative, find the index i.

Input:

10
5 6 7 -2 -8 -1 -4 -3 -5 -6

Output:

2 

output is 2 because arr[2]=7 which is last positive number in given array.

In this question array is not sorted but still we can solve using binary search.

Solution Code:

bool f(vector<int>& arr, int mid) {
    return arr[mid] >= 0;
}

int solve(vector<int>& arr, int n) {
    int low = 0, high = n — 1;
    if (arr[0] < 0) return -1;
    if (arr[n — 1] >= 0) return n — 1;
    int ans = -1;
    while (low <= high) {
        int mid = low + (high — low) / 2;
        if (f(arr, mid)) {
            ans = mid;
            low = mid + 1;
        } else {
            high = mid — 1;
        }
    }
    return ans;
}

Explanation of the Code

The function f checks if the element at the middle index is non-negative. The solve function performs the binary search:

• Edge Case 1: If the first element is negative, return -1 immediately, as there are no non-negative numbers in the array.
• Edge Case 2: If the last element is non-negative, return n — 1, as all elements in the array are non-negative.
• Binary Search Initialization: Set low = 0 and high = n — 1 to define the search space. Initialize ans = -1 to store the last valid index.
• Mid Calculation: Compute mid = low + (high — low) / 2 to avoid overflow and find the middle index.
• Condition Check: Use the function f to check if arr[mid] >= 0. If true, update ans = mid and move low = mid + 1 to search for a better (higher) valid index.
• Else Condition: If f returns false, move high = mid — 1 to search in the left half, as the current mid is not valid.
• Termination: The loop runs until low exceeds high. At this point, ans holds the last valid index where arr[mid] >= 0.

This approach ensures the search space is halved in each iteration, making the algorithm efficient with a time complexity of O(log n).

What’s New in Binary Search?

Binary search can be adapted to various problems by modifying the condition function and the update logic. Practice problems where you need to find the first or last occurrence of an element, or apply binary search on a function's output.

Practice Template

while (low <= high) {
    int mid = low + (high — low) / 2;
    if (condition(arr, mid)) {
        // Update low or high based on the problem
    } else {
        // Update low or high based on the problem
    }
}
return low; // or high, depending on the problem

What’s Next?

This blog for basic idea about Binary Search In the next blog, we will dive deeper into binary search techniques, including:

• Binary search on answer space (e.g., finding the minimum or maximum value satisfying a condition).
• Binary search on 2D arrays or matrices.
• Solve Good Question which can help to increase skill in Binary Search Problems

Happy coding!