Binary Search in Action

In Binary Search Framework Explained, we delved into the details of binary search, discussing the three scenarios: "searching for an element," "searching for the left boundary," and "searching for the right boundary." This teaches you how to write a bug-free binary search algorithm.

However, the binary search code framework summarized in the previous article is limited to the basic scenario of "searching for a specific element in a sorted array." Real algorithm problems are not always so straightforward, and you might find it hard to recognize that binary search can be applied.

Therefore, this article aims to provide a systematic framework for applying binary search algorithms. It will help you think and analyze methodically when encountering binary search-related problems in practice, allowing you to solve them step by step.

Basic Binary Search Code

Binary search is fundamentally about searching for an element target in a sorted array and returning the index of that element.

If the element doesn't exist, you can return a special value. These kinds of details can be easily adjusted in the algorithm implementation.

Another important issue is when there are multiple occurrences of target in the sorted array. These elements will be adjacent. This raises the question of whether the algorithm should return the index of the leftmost target or the rightmost target, known as "searching for the left boundary" and "searching for the right boundary." This can also be achieved by tweaking the algorithm code.

We discussed these issues in detail in our previous article Binary Search Core Framework. Readers who are not clear about this are advised to review the previous article. Those who already understand the basic binary search algorithm can continue reading.

In specific algorithm problems, the common scenarios are 'searching for the left boundary' and 'searching for the right boundary.' It's rare to be asked to 'search for a single element' alone.

This is because algorithm problems often require finding the extreme values, such as the 'minimum speed' for eating bananas or the 'minimum carrying capacity' of a ship. The process of finding these extreme values inherently involves searching for a boundary. Therefore, we will delve into the detailed analysis of these two boundary search binary algorithm codes.

The specific code implementation for the binary search algorithm that searches for the left boundary is as follows:

// search for the left boundary
int left_bound(int[] nums, int target) {
    if (nums.length == 0) return -1;
    int left = 0, right = nums.length;
    
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            // when target is found, shrink the right boundary
            right = mid;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid;
        }
    }
    return left;
}

// search for the left boundary
int left_bound(vector<int>& nums, int target) {
    if (nums.size() == 0) return -1;
    int left = 0, right = nums.size();
    
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            // when target is found, shrink the right boundary
            right = mid;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid;
        }
    }
    return left;
}

def left_bound(nums: List[int], target: int) -> int:
    # search for the left boundary
    if len(nums) == 0:
        return -1
    left, right = 0, len(nums)
    while left < right:
        mid = left + (right - left) // 2
        if nums[mid] == target:
            # when target is found, shrink the right boundary
            right = mid
        elif nums[mid] < target:
            left = mid + 1
        elif nums[mid] > target:
            right = mid
    return left

// Search for the left boundary
func left_bound(nums []int, target int) int {
    if len(nums) == 0 {
        return -1
    }

    left, right := 0, len(nums)    
    for left < right {
        mid := left + (right - left) / 2
        if nums[mid] == target {
            // When target is found, shrink the right boundary
            right = mid
        } else if nums[mid] < target {
            left = mid + 1
        } else if nums[mid] > target {
            right = mid
        }
    }
    return left
}

// search for the left boundary
var left_bound = function(nums, target) {
    if (nums.length === 0) return -1;
    let left = 0, right = nums.length;
    
    while (left < right) {
        let mid = left + Math.floor((right - left) / 2);
        if (nums[mid] === target) {
            // when target is found, shrink the right boundary
            right = mid;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid;
        }
    }
    return left;
};

Suppose the input array is nums = [1,2,3,3,3,5,7], and the element you want to search for is target = 3. The algorithm will return index 2.

If you draw a diagram, it looks like this:

Here is the specific code implementation of the "searching for the right boundary" binary search algorithm:

// search for the right boundary
int right_bound(int[] nums, int target) {
    if (nums.length == 0) return -1;
    int left = 0, right = nums.length;

    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            // when target is found, shrink the left boundary
            left = mid + 1;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid;
        }
    }
    return left - 1;
}

// search for the right boundary
int right_bound(vector<int>& nums, int target) {
    if (nums.size() == 0) return -1;
    int left = 0, right = nums.size();

    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            // when target is found, shrink the left boundary
            left = mid + 1;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid;
        }
    }
    return left - 1;
}

# Search for the right boundary
def right_bound(nums: list[int], target: int) -> int:
    if len(nums) == 0:
        return -1
    left, right = 0, len(nums)

    while left < right:
        mid = left + (right - left) // 2
        if nums[mid] == target:
            # When target is found, shrink the left boundary
            left = mid + 1
        elif nums[mid] < target:
            left = mid + 1
        elif nums[mid] > target:
            right = mid
    return left - 1

// Search for the right boundary
func right_bound(nums []int, target int) int {
    if len(nums) == 0 {
        return -1
    }
    left, right := 0, len(nums)

    for left < right {
        mid := left + (right-left)/2
        if nums[mid] == target {
            // When target is found, shrink the left boundary
            left = mid + 1
        } else if nums[mid] < target {
            left = mid + 1
        } else if nums[mid] > target {
            right = mid
        }
    }
    return left - 1
}

// search for the right boundary
var right_bound = function(nums, target) {
    if (nums.length === 0) return -1;
    let left = 0, right = nums.length;
    
    while (left < right) {
        let mid = left + Math.floor((right - left) / 2);
        if (nums[mid] === target) {
            // when target is found, shrink the left boundary
            left = mid + 1;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid;
        }
    }
    return left - 1;
};

With the input as mentioned above, the algorithm will return index 4. If we draw a diagram, it looks like this:

Good, the content above serves as a review. Readers who have reached this point should understand it. Remember the image above; any problem that can be abstracted into this image can be solved using binary search.