Binary Search Algorithm Code Template

This article is a revised version of the article 二分搜索详解, adding a more detailed analysis of the binary search algorithm.

Let me start with a joke:

One day, Dong borrowed N books from the library. As he was leaving, the alarm went off, so the security guard stopped him to check which book wasn't registered. Dong was about to pass each book through the alarm one by one to find the one causing the alarm, but the security guard looked at him disdainfully: "Don't you even know binary search?"

So, the security guard divided the books into two piles and passed the first pile through the alarm. The alarm went off, indicating the book causing the alarm was in this pile. He then divided this pile into two and passed the first half through the alarm again. The alarm went off once more, and he continued dividing into two piles...

After logN checks, the guard successfully found the book that triggered the alarm and gave a smug and mocking smile. Dong walked away with the remaining books.

From then on, the library lost N - 1 books (manually adding a humorous touch).

Binary search is not simple. Even Knuth, the inventor of the KMP algorithm, said about binary search: The idea is simple, but the devil is in the details. Many people focus on integer overflow bugs, but the real issue in binary search is not that detail. It is about whether to add or subtract one from mid, and whether to use <= or < in the while loop.

If you do not understand these details correctly, writing binary search becomes a mystical exercise, with bugs only avoidable by sheer luck. Anyone who has written it knows this.

This article explores several common scenarios for binary search: finding a number, finding the left boundary, and finding the right boundary. We will delve into the details, such as whether inequality should include equality, whether mid should be incremented, etc. Analyzing these detailed differences and their reasons ensures you can write a correct binary search algorithm flexibly and accurately.

Additionally, for each binary search scenario, this article will discuss multiple coding approaches. The aim is to help you understand the fundamental reasons for these subtle differences, so you won't be confused by other people's code. In practice, there is no best approach; use whichever you prefer.

Zero, Binary Search Framework

int binarySearch(int[] nums, int target) {
    int left = 0, right = ...;

    while(...) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            ...
        } else if (nums[mid] < target) {
            left = ...
        } else if (nums[mid] > target) {
            right = ...
        }
    }
    return ...;
}

int binarySearch(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;

    while (...) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            ...
        } else if (nums[mid] < target) {
            left = ...
        } else if (nums[mid] > target) {
            right = ...
        }
    }
}

def binarySearch(nums: List[int], target: int) -> int:
    left, right = 0, len(nums) - 1

    while ...:
        mid = left + (right - left) // 2
        if nums[mid] == target:
            ...
        elif nums[mid] < target:
            left = ...
        elif nums[mid] > target:
            right = ...
    return ...

func binarySearch(nums []int, target int) int {
    left, right := 0, len(nums)-1

    for left <= right {
        mid := left + (right-left)/2
        if nums[mid] == target {
            ...
        } else if nums[mid] < target {
            left = ...
        } else if nums[mid] > target {
            right = ...
        }
    }
    return ...
}

var binarySearch = function(nums, target) {
    var left = 0, right = nums.length - 1;

   while (...) {
        var mid = left + Math.floor((right - left) / 2);
        if (nums[mid] == target) {
            ...
        } else if (nums[mid] < target) {
            left = ...
        } else if (nums[mid] > target) {
            right = ...
        }
    }
    return ...;
}

One technique for analyzing binary search is: do not use else; instead, use else if to clearly outline all scenarios. This way, all details are clearly presented. This article will use else if to clarify, but once understood, readers can simplify it themselves.

The parts marked with ... are where potential detail issues might occur. When you see a binary search code, pay attention to these areas first. Later in this article, we will use examples to analyze what variations can occur in these parts.

Additionally, note that when calculating mid, overflow needs to be prevented. The code left + (right - left) / 2 yields the same result as (left + right) / 2, but effectively prevents overflow caused by directly adding very large left and right.

I. Finding a Number (Basic Binary Search)

This scenario is the simplest and possibly the most familiar: searching for a number and returning its index if it exists, otherwise returning -1.

class Solution {
    // standard binary search framework, search for the
    // index of the target element, return -1 if it does not
    public int search(int[] nums, int target) {
        int left = 0;
        // note
        int right = nums.length - 1;

        while(left <= right) {
            int mid = left + (right - left) / 2;
            if(nums[mid] == target) {
                return mid;   
            } else if (nums[mid] < target) {
                // note
                left = mid + 1;
            } else if (nums[mid] > target) {
                // note
                right = mid - 1;
            }
        }
        return -1;
    }
}

class Solution {
public:
    // standard binary search framework, search for the
    // index of the target element, return -1 if it does not
    int search(vector<int>& nums, int target) {
        int left = 0;
        // note
        int right = nums.size() - 1;

        while(left <= right) {
            int mid = left + (right - left) / 2;
            if(nums[mid] == target) {
                return mid;   
            } else if (nums[mid] < target) {
                // note
                left = mid + 1;
            } else if (nums[mid] > target) {
                // note
                right = mid - 1;
            }
        }
        return -1;
    }
};

class Solution:
    # standard binary search framework, search for the
    # index of the target element, return -1 if it does not
    def search(self, nums: List[int], target: int) -> int:
        left = 0
        # note
        right = len(nums) - 1

        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] == target:
                return mid
            elif nums[mid] < target:
                # note
                left = mid + 1
            elif nums[mid] > target:
                # note
                right = mid - 1
        return -1

// standard binary search framework, search for the index
// of the target element, return -1 if it does not exist
func search(nums []int, target int) int {
    left := 0
    // note
    right := len(nums) - 1

    for left <= right {
        mid := left + (right-left)/2
        if nums[mid] == target {
            return mid
        } else if nums[mid] < target {
            // note
            left = mid + 1
        } else if nums[mid] > target {
            // note
            right = mid - 1
        }
    }
    return -1
}

var search = function(nums, target) {
    // standard binary search framework, search for the
    // index of the target element, return -1 if it does not
    let left = 0;
    // note
    let right = nums.length - 1;

    while (left <= right) {
        let mid = left + Math.floor((right - left) / 2);
        if (nums[mid] === target) {
            return mid;
        } else if (nums[mid] < target) {
            // note
            left = mid + 1;
        } else if (nums[mid] > target) {
            // note
            right = mid - 1;
        }
    }
    return -1;
};

This code can solve LeetCode Problem 704, "Binary Search", but let's delve deeper into its details.

Why is the condition in the while loop <= instead of <?

Answer: Because the initialization of right is assigned as nums.length - 1, which is the index of the last element, not nums.length.

These two may appear in different types of binary search functions. The difference is: the former corresponds to a closed interval on both ends [left, right], while the latter corresponds to a half-open interval [left, right). Since an index of nums.length is out of bounds, we consider the right side as an open interval.

In our algorithm, we use the former [left, right] which is a closed interval on both ends. This interval is essentially the search range for each iteration.

When should we stop the search? Of course, we can terminate when the target value is found:

    if(nums[mid] == target)
        return mid;

However, if the target is not found, the while loop needs to terminate and return -1. When should the while loop terminate? It should terminate when the search interval is empty, meaning there's nothing left to search, which implies the target is not found.

The termination condition for while(left <= right) is left == right + 1. In interval form, this is [right + 1, right], or with a specific number, [3, 2]. Clearly, the interval is empty at this point, as no number can be both greater than or equal to 3 and less than or equal to 2. Therefore, terminating the while loop here is correct, and you can directly return -1.

The termination condition for while(left < right) is left == right. In interval form, this is [right, right], or with a specific number, [2, 2]. The interval is not empty here, as it contains the number 2, but the while loop terminates. This means the interval [2, 2] is missed, and index 2 is not searched. Returning -1 directly in this case would be incorrect.

Of course, if you insist on using while(left < right), that's also possible. We already know the cause of the error, so we can apply a fix:

    // ...
    while(left < right) {
        // ...
    }
    return nums[left] == target ? left : -1;

Why left = mid + 1 and right = mid - 1?

Why do we use left = mid + 1 and right = mid - 1? I've seen some code where right = mid or left = mid without these additions and subtractions. What's going on, and how do we decide?

Answer: This is indeed a tricky part of binary search, but if you understand the previous content, it becomes easy to determine.

We previously clarified the concept of the "search interval," and in this algorithm, the search interval is closed on both ends, i.e., [left, right]. So, when we find that the index mid is not the target we are looking for, where should we search next?

Obviously, we should search in the interval [left, mid-1] or [mid+1, right], right? **Because mid` has already been searched, it should be removed from the search interval.**

What Are the Limitations of This Algorithm?

Answer: By now, you should have mastered all the details of this algorithm and the reasons behind its design. However, this algorithm has limitations.

For example, given a sorted array nums = [1,2,2,2,3] and a target of 2, the algorithm returns the index 2, which is correct. But what if I want to find the left boundary of the target, which is index 1, or the right boundary, which is index 3? This algorithm cannot handle such cases.

These requirements are common. You might say, "Can't we just find a target and then search linearly to the left or right?" Yes, you can, but it's not efficient because it breaks the logarithmic complexity of binary search.

In our subsequent discussions, we will cover two variations of binary search to address these issues.

II. Binary Search for Finding the Left Boundary

Here is the most common form of the code, with annotations highlighting the details to pay attention to:

int left_bound(int[] nums, int target) {
    int left = 0;
    // note
    int right = nums.length;
    
    // note
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            right = mid;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            // note
            right = mid;
        }
    }
    return left;
}

int left_bound(vector<int>& nums, int target) {
    int left = 0;
    // note
    int right = nums.size();
    
    // note
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            right = mid;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            // note
            right = mid;
        }
    }
    return left;
}

def left_bound(nums: List[int], target: int) -> int:
    left = 0
    # note
    right = len(nums)
    
    # note
    while left < right:
        mid = left + (right - left) // 2
        if nums[mid] == target:
            right = mid
        elif nums[mid] < target:
            left = mid + 1
        elif nums[mid] > target:
            # note
            right = mid

    return left

func left_bound(nums []int, target int) int {
    left := 0
    // note
    right := len(nums)
    
    // note
    for left < right {
        mid := left + (right - left) / 2
        if nums[mid] == target {
            right = mid
        } else if nums[mid] < target {
            left = mid + 1
        } else if nums[mid] > target {
            // note
            right = mid
        }
    }
    return left
}

var left_bound = function(nums, target) {
    var left = 0;
    // note
    var right = nums.length;
    
    // note
    while (left < right) {
        var mid = left + Math.floor((right - left) / 2);
        if (nums[mid] == target) {
            right = mid;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            // note
            right = mid;
        }
    }
    return left;
}

Why Use < Instead of <= in the while Loop?

Answer: Analyzing in the same way, because right = nums.length rather than nums.length - 1. Therefore, the "search interval" in each loop is [left, right), which is left-closed and right-open.

The termination condition for while(left < right) is left == right, at which point the search interval [left, left) is empty, allowing for correct termination.

What to Return if target Does Not Exist?

If the value target does not exist in nums, what does the calculated index represent? How can I make it return -1?

// Find the index of the largest element less than target in a sorted array
// For example, input nums = [1,2,2,2,3], target = 2, the
// function returns 0 because 1 is the largest element less than
// Another example, input nums = [1,2,3,5,6], target = 4, the
// function returns 2 because 3 is the largest element less than
int floor(int[] nums, int target) {
    // When target does not exist, for example, input [4,6,8,10], target = 7
    // left_bound returns 2, subtract one to get 1,
    // the element 6 is the largest element less than
    // When target exists, for example, input [4,6,8,8,8,10], target = 8
    // left_bound returns 2, subtract one to get 1,
    // the element 6 is the largest element less than
    return left_bound(nums, target) - 1;
}

To return -1 when target does not exist is actually quite simple. Just add an extra check when returning to see if nums[left] equals target. If it does not, then target does not exist. It's important to ensure the index is within bounds before accessing the array index:

while (left < right) {
    // ...
}
// if the index is out of bounds, it means there is no target element in the array, return -1
if (left < 0 || left >= nums.length) {
    return -1;
}
// note: actually, the judgment of left < 0 in the above if can be
// omitted, because for this algorithm, left cannot be less than 0
// as you can see, the logic of this algorithm is that left is initialized to 0 and
// can only keep moving to the right, so it can only go out of bounds on the right side
// however, I've judged both here, because ensuring that the index is not out of
// bounds at both ends before accessing the array index is a good habit with no
// another benefit is that it makes the binary search template more unified, reducing the memory
// cost, because there will be similar out-of-bounds judgments when looking for the right boundary

// determine if nums[left] is the target
return nums[left] == target ? left : -1;

Why left = mid + 1 and right = mid?

Why do we use left = mid + 1 and right = mid? Isn't this different from previous algorithms?

Answer: This is quite straightforward. Our "search interval" is [left, right) which is left-closed and right-open. After checking nums[mid], the next step should be to search either the left or right side of mid, specifically [left, mid) or [mid + 1, right).

Why does this algorithm find the left boundary?

Answer: The key lies in how we handle the case when nums[mid] == target:

    if (nums[mid] == target)
        right = mid;

As you can see, instead of returning immediately when we find the target, we narrow the upper bound of the "search interval" by setting right to mid. This continues the search within the interval [left, mid), effectively shrinking the interval to the left, thereby locking in the left boundary.

Why Return left Instead of right?

Answer: Both are the same because the while loop terminates when left == right.

Can We Use a Closed Search Interval on Both Ends?

Is it possible to change right to nums.length - 1, meaning we continue to use a "search interval" that is closed on both ends? This way, it can be unified with the first type of binary search to some extent.

Answer: Of course! As long as you understand the concept of a "search interval," you can effectively avoid missing elements, and you can modify it however you like. Let's strictly follow the logic to make the changes:

Since you insist on having a closed search interval on both ends, right should be initialized to nums.length - 1. The termination condition for the while loop should be left == right + 1, which means you should use <=:

int left_bound(int[] nums, int target) {
    // the search range is [left, right]
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        // if else ...
    }
}

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

def left_bound(nums: List[int], target: int) -> int:
    # the search interval is [left, right]
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = left + (right - left) // 2
        # if else ...

func left_bound(nums []int, target int) int {
    // the search interval is [left, right]
    left, right := 0, len(nums)-1
    for left <= right {
        mid := left + (right-left)/2
        // if else ...
    }
}

var left_bound = function(nums, target) {
    // the search range is [left, right]
    var left = 0, right = nums.length - 1;
    while (left <= right) {
        var mid = left + Math.floor((right - left) / 2);
        // if else ...
    }
}

Since the search interval is closed on both ends and we are currently searching for the left boundary, the update logic for left and right is as follows:

if (nums[mid] < target) {
    // the search range becomes [mid+1, right]
    left = mid + 1;
} else if (nums[mid] > target) {
    // the search range becomes [left, mid-1]
    right = mid - 1;
} else if (nums[mid] == target) {
    // shrink the right boundary
    right = mid - 1;
}

if (nums[mid] < target) {
    // the search range becomes [mid+1, right]
    left = mid + 1;
} else if (nums[mid] > target) {
    // the search range becomes [left, mid-1]
    right = mid - 1;
} else if (nums[mid] == target) {
    // shrink the right boundary
    right = mid - 1;
}

if nums[mid] < target:
    # the search range becomes [mid+1, right]
    left = mid + 1
elif nums[mid] > target:
    # the search range becomes [left, mid-1]
    right = mid - 1
elif nums[mid] == target:
    # shrink the right boundary
    right = mid - 1

if nums[mid] < target {
    // the search range becomes [mid+1, right]
    left = mid + 1
} else if nums[mid] > target {
    // the search range becomes [left, mid-1]
    right = mid - 1
} else if nums[mid] == target {
    // shrink the right boundary
    right = mid - 1
}

if (nums[mid] < target) {
    // the search range becomes [mid+1, right]
    left = mid + 1;
} else if (nums[mid] > target) {
    // the search range becomes [left, mid-1]
    right = mid - 1;
} else if (nums[mid] == target) {
    // shrink the right boundary
    right = mid - 1;
}

Similarly, if you want to return -1 when target is not found, simply check if nums[left] is equal to target:

// at this point, target is larger than all numbers, return -1
if (left == nums.length) return -1;
// determine if nums[left] is the target
return nums[left] == target ? left : -1;

// at this point, target is larger than all numbers, return -1
if (left == nums.size()) return -1;
// determine if nums[left] is the target
return nums[left] == target ? left : -1;

# at this point, target is larger than all numbers, return -1
if left == len(nums):
    return -1
# determine if nums[left] is the target
return left if nums[left] == target else -1

// at this point, target is larger than all numbers, return -1
if left == len(nums) {
  return -1
}
// determine if nums[left] is the target
if nums[left] == target {
  return left
} else {
  return -1
}

// When the left pointer reaches the end of the array, the target
// must be larger than all the numbers in the array, return -1.
if (left === nums.length) return -1;
// If the target is found, return its index, otherwise return -1.
return nums[left] === target ? left : -1;

Now, the entire algorithm is complete. Here is the full code:

int left_bound(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    // the search range is [left, right]
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            // the search range becomes [mid+1, right]
            left = mid + 1;
        } else if (nums[mid] > target) {
            // the search range becomes [left, mid-1]
            right = mid - 1;
        } else if (nums[mid] == target) {
            // shrink the right boundary
            right = mid - 1;
        }
    }
    // determine if target exists in nums
    // if out of bounds, target definitely does not exist, return -1
    if (left < 0 || left >= nums.length) {
        return -1;
    }
    // check if nums[left] is the target
    return nums[left] == target ? left : -1;
}

int left_bound(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
    // the search range is [left, right]
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            // the search range becomes [mid+1, right]
            left = mid + 1;
        } else if (nums[mid] > target) {
            // the search range becomes [left, mid-1]
            right = mid - 1;
        } else if (nums[mid] == target) {
            // shrink the right boundary
            right = mid - 1;
        }
    }
    // determine if target exists in nums
    // if out of bounds, target definitely does not exist, return -1
    if (left < 0 || left >= nums.size()) {
        return -1;
    }
    // check if nums[left] is target
    return nums[left] == target ? left : -1;
}

def left_bound(nums: List[int], target: int) -> int:
    left, right = 0, len(nums) - 1
    # the search range is [left, right]
    
    while left <= right:
        mid = left + (right - left) // 2
        if nums[mid] < target:
            # the search range becomes [mid+1, right]
            left = mid + 1
        elif nums[mid] > target:
            # the search range becomes [left, mid-1]
            right = mid - 1
        elif nums[mid] == target:
            # shrink the right boundary
            right = mid - 1
    
    # determine if target exists in nums
    # if out of bounds, target definitely does not exist, return -1
    if left < 0 or left >= len(nums):
        return -1
    
    # determine if nums[left] is target
    return left if nums[left] == target else -1

// Search for the left boundary of the target in the given nums
func left_bound(nums []int, target int) int {
    left := 0
    right := len(nums) - 1
    // the search range is [left, right]
    for left <= right {
        mid := left + (right - left) / 2
        if nums[mid] < target {
            // the search range becomes [mid+1, right]
            left = mid + 1
        } else if nums[mid] > target {
            // the search range becomes [left, mid-1]
            right = mid - 1
        } else if nums[mid] == target {
            // shrink the right boundary
            right = mid - 1
        }
    }
    // determine if the target exists in nums
    if left < 0 || left >= len(nums) {
        return -1
    }
    // if out of bounds, the target definitely does not exist, return -1
    if nums[left] == target {
        // determine if nums[left] is the target
        return left
    }
    return -1
}

var left_bound = function(nums, target) {
    var left = 0, right = nums.length - 1;
    // the search range is [left, right]
    while (left <= right) {
        var mid = left + Math.floor((right - left) / 2);
        if (nums[mid] < target) {
            // the search range becomes [mid+1, right]
            left = mid + 1;
        } else if (nums[mid] > target) {
            // the search range becomes [left, mid-1]
            right = mid - 1;
        } else if (nums[mid] == target) {
            // shrink the right boundary
            right = mid - 1;
        }
    }
    // determine if target exists in nums
    // if out of bounds, target definitely does not exist, return -1
    if (left < 0 || left >= nums.length) {
        return -1;
    }
    // check if nums[left] is target
    return nums[left] == target ? left : -1;
};

This way, it aligns with the first binary search algorithm, both using a closed "search interval" on both ends, and the final return value is also the value of the left variable. As long as you grasp the logic of binary search, you can choose whichever form you prefer.

Three, Binary Search for Finding the Right Boundary

Similar to the algorithm for finding the left boundary, this section will also provide two implementations. We'll start with the common left-closed-right-open approach, which differs from the left boundary search in only two places:

int right_bound(int[] nums, int target) {
    int left = 0, right = nums.length;
    
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            // note
            left = mid + 1;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid;
        }
    }
    // note
    return left - 1;
}

int right_bound(vector<int>& nums, int target) {
    int left = 0, right = nums.size();

    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            // note
            left = mid + 1;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid;
        }
    }
    // note
    return left - 1;
}

def right_bound(nums, target):
    left, right = 0, len(nums)
    while left < right:
        mid = left + (right - left) // 2
        if nums[mid] == target:
            # note
            left = mid + 1
        elif nums[mid] < target:
            left = mid + 1
        elif nums[mid] > target:
            right = mid
    # note
    return left - 1

func right_bound(nums []int, target int) int {
    left, right := 0, len(nums)
    for left < right {
        mid := left + (right - left) / 2
        if nums[mid] == target {
            // note
            left = mid + 1
        } else if nums[mid] < target {
            left = mid + 1
        } else if nums[mid] > target {
            right = mid
        }
    }
    // note
    return left - 1
}

var right_bound = function(nums, target) {
    var left = 0, right = nums.length;
    
    while (left < right) {
        var mid = left + Math.floor((right - left) / 2);
        if (nums[mid] === target) {
            // note
            left = mid + 1;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid;
        }
    }
    // note
    return left - 1;
}

Why Does This Algorithm Find the Right Boundary?

Answer: Similarly, the key point is here:

if (nums[mid] == target) {
    left = mid + 1;
}

When nums[mid] == target, instead of returning immediately, increase the left boundary left of the "search interval" to make the interval gradually shift to the right. This achieves the goal of locking the right boundary.

Why Return left - 1?

Why do we return left - 1 at the end instead of left like the left boundary function? Moreover, I think since we are searching for the right boundary, we should return right.

Answer: First, the while loop terminates when left == right, so left and right are the same. If you really want to emphasize the right side, you can return right - 1.

As for why we subtract one, this is a special point in searching for the right boundary. The key is in this condition check when locking the right boundary:

// Increase left, lock the right boundary
if (nums[mid] == target) {
    left = mid + 1;
    // Think this way: mid = left - 1
}

Since our update for left must be left = mid + 1, it means that when the while loop ends, nums[left] is certainly not equal to target, but nums[left-1] might be target.

As for why the update for left must be left = mid + 1, it is to exclude nums[mid] from the search interval, which will not be elaborated here.

What to Return if target Does Not Exist?

If target does not exist in nums, what does the calculated index mean? How can it return -1 if desired?

If you want to return -1 when target does not exist, it's simple: just check at the end if nums[left-1] is target, similar to the left boundary search, with a little additional check:

while (left < right) {
    // ...
}
// determine if target exists in nums
// if left - 1 is out of bounds, target definitely does not exist
if (left - 1 < 0 || left - 1 >= nums.length) {
    return -1;
}
// check if nums[left - 1] is the target
return nums[left - 1] == target ? (left - 1) : -1;

while (left < right) {
    // ...
}
// determine if target exists in nums
// if left - 1 index is out of bounds, target definitely does not exist
if (left - 1 < 0 || left - 1 >= nums.size()) {
    return -1;
}
// check if nums[left - 1] is the target
return nums[left - 1] == target ? (left - 1) : -1;

while left < right:
    # ...
# determine if target exists in nums
# if left - 1 index is out of bounds, target definitely does not exist
if left - 1 < 0 or left - 1 >= len(nums):
    return -1
# check if nums[left - 1] is target
return left - 1 if nums[left - 1] == target else -1

for left < right {
    // ...
}
// determine if target exists in nums
// if left - 1 is out of bounds, target definitely does not exist
if left-1 < 0 || left-1 >= len(nums) {
    return -1
}
// check if nums[left - 1] is target
if nums[left-1] == target {
    return left - 1
} else {
    return -1
}

var func = function() {
  while (left < right) {
    // ...
  }
  // determine if target exists in nums
  // if left - 1 is out of bounds, target definitely does not exist
  if (left - 1 < 0 || left - 1 >= nums.length) {
      return -1;
  }
  // check if nums[left - 1] is the target
  return nums[left - 1] == target ? (left - 1) : -1;
}

4. Can the "search range" of this algorithm also be unified to a closed interval on both ends? This way, the three implementations would be completely consistent, and you could write them effortlessly in the future.

Answer: Absolutely, similar to the unified approach for searching the left boundary, you only need to change two things:

int right_bound(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else if (nums[mid] == target) {
            // here change to shrink the left boundary
            left = mid + 1;
        }
    }
    // finally change to return left - 1
    if (left - 1 < 0 || left - 1 >= nums.length) {
        return -1;
    }
    return nums[left - 1] == target ? (left - 1) : -1;
}

int right_bound(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else if (nums[mid] == target) {
            // here, change it to shrink the left boundary
            left = mid + 1;
        }
    }
    // finally, change it to return left - 1
    if (left - 1 < 0 || left - 1 >= nums.size()) {
        return -1;
    }
    return nums[left - 1] == target ? (left - 1) : -1;
}

def right_bound(nums: List[int], target: int) -> int:
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = left + (right - left) // 2
        if nums[mid] < target:
            left = mid + 1
        elif nums[mid] > target:
            right = mid - 1
        elif nums[mid] == target:
            # here, change it to shrink the left boundary
            left = mid + 1
    # finally, change it to return left - 1
    if left - 1 < 0 or left - 1 >= len(nums):
        return -1
    return left - 1 if nums[left - 1] == target else -1

func rightBound(nums []int, target int) int {
    left, right := 0, len(nums) - 1
    for left <= right {
        mid := left + (right - left) / 2
        if nums[mid] < target {
            left = mid + 1
        } else if nums[mid] > target {
            right = mid - 1
        } else if nums[mid] == target {
            // here, just shrink the left boundary
            left = mid + 1
        }
    }
    // finally, return left - 1
    if left - 1 < 0 || left - 1 >= len(nums) {
        return -1
    }
    if nums[left - 1] == target {
        return left - 1
    }
    return -1
}

var right_bound = function(nums, target) {
    var left = 0, right = nums.length - 1;
    while (left <= right) {
        var mid = left + Math.floor((right - left) / 2);
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else if (nums[mid] == target) {
            // change here to shrink the left boundary
            left = mid + 1;
        }
    }
    // finally, change to return left - 1
    if (left - 1 < 0 || left - 1 >= nums.length) {
        return -1;
    }
    return nums[left - 1] == target ? (left - 1) : -1;
};

Of course, since the termination condition of the while loop is right == left - 1, you can also change all instances of left - 1 in the above code to right. This might make it easier to see that this is for "searching the right boundary":

int right_bound(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else if (nums[mid] == target) {
            // here change to shrink the left boundary
            left = mid + 1;
        }
    }
    // finally change to return right
    if (right < 0 || right >= nums.length) {
        return -1;
    }
    return nums[right] == target ? right : -1;
}

Thus, two ways of implementing the binary search for the right boundary are completed. In fact, unifying the "search interval" to be closed at both ends is easier to remember, don't you think?

IV. Logical Unification

With the binary search for both the left and right boundaries, you can solve LeetCode Problem 34: "Find First and Last Position of Element in Sorted Array". Let's sort out the causal logic of these subtle differences:

First, the most basic binary search algorithm:

因为我们初始化 right = nums.length - 1
所以决定了我们的「搜索区间」是 [left, right]
所以决定了 while (left <= right)
同时也决定了 left = mid+1 和 right = mid-1

因为我们只需找到一个 target 的索引即可
所以当 nums[mid] == target 时可以立即返回

Second, Binary Search for Finding the Left Boundary:

因为我们初始化 right = nums.length
所以决定了我们的「搜索区间」是 [left, right)
所以决定了 while (left < right)
同时也决定了 left = mid + 1 和 right = mid

因为我们需找到 target 的最左侧索引
所以当 nums[mid] == target 时不要立即返回
而要收紧右侧边界以锁定左侧边界

Third, Binary Search for Finding the Right Boundary:

因为我们初始化 right = nums.length
所以决定了我们的「搜索区间」是 [left, right)
所以决定了 while (left < right)
同时也决定了 left = mid + 1 和 right = mid

因为我们需找到 target 的最右侧索引
所以当 nums[mid] == target 时不要立即返回
而要收紧左侧边界以锁定右侧边界

又因为收紧左侧边界时必须 left = mid + 1
所以最后无论返回 left 还是 right，必须减一

For binary search to find left and right boundaries, a common approach is to use a "search interval" that is left-closed and right-open. We have also unified all "search intervals" to be closed on both ends for easier memorization. By modifying just two places, you can derive three different implementations:

If you can understand all the content above, congratulations! The details of the binary search algorithm are just that. Through this article, you have learned:

1. When analyzing binary search code, avoid using else; expand everything into else if for better understanding. After getting the logic right, combine branches to improve runtime efficiency.

2. Pay attention to the "search interval" and the termination condition of the while loop. If there are any missing elements, remember to check at the end.

3. If you need to define a left-closed right-open "search interval" to search for boundaries, just modify the code when nums[mid] == target. When searching the right boundary, subtract one.

4. If you unify the "search interval" to be closed on both ends, it's easier to remember. Just slightly modify the code at the nums[mid] == target condition and the return logic. It's recommended to jot this down as a binary search template.

Finally, I want to say that the above binary search framework belongs to the category of "technique". If we elevate it to the level of "principle", the essence of binary thinking is: to shrink (halve) the search space as much as possible through known information, thereby increasing the efficiency of exhaustive search and quickly finding the target.

Understanding this article can ensure that you write correct binary search code. However, in actual problems, you won't be directly asked to write binary search code. I will further explain how to apply binary thinking to more algorithm problems in Binary Search Applications and More Binary Search Exercises.