Binary Search Algorithm Code Template

This article is a revised version of the article Detailed Explanation of Binary Search, adding a more detailed analysis of the binary search algorithm.

Let me start with a joke to lighten the mood:

One day, Ah-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 hadn't been properly checked out. Ah-Dong was about to scan each book individually under the alarm to find the culprit, but the security guard gave him a disdainful look: "Don't you know how to use binary search?"

The security guard then divided the books into two piles and scanned the first pile under the alarm. The alarm went off, indicating the problematic book was in that pile. He then divided that pile into two and scanned the first half again. The alarm went off once more, so he continued dividing the pile...

Finally, after logN scans, the security guard successfully identified the book that triggered the alarm, with a smug and mocking smile on his face. Ah-Dong then left with the remaining books.

Since then, the library lost N - 1 books (just kidding).

Binary search is not as simple as it seems. 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 like to talk about integer overflow bugs, but the real pitfall of binary search is not in those minor details. It's 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 endeavor, with bugs left to chance. Anyone who has written it knows the struggle.

This article explores several of the most common binary search scenarios: finding a number, finding the left boundary, and finding the right boundary. We will delve into the details, such as whether inequality signs should include an equal sign, and whether mid should be incremented. Analyzing these differences and their causes will ensure you can write binary search algorithms accurately and flexibly.

Additionally, for each binary search scenario, the article will discuss various code implementations. The aim is to help you understand the fundamental reasons for these subtle differences so that you won't be confused when you see others' code. In fact, there is no superior or inferior way to write it; use whichever method 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 ...;
}

A key technique in analyzing binary search is to avoid using else, and instead write all cases with else if to clearly show all details. This article will use else if to ensure clarity, and readers can simplify it after understanding.

The parts marked with ... are where detail issues might arise. When you see a binary search code, pay attention to these areas first. The following sections will analyze examples to show how these areas can vary.

Also, a heads-up: when calculating mid, you need to prevent overflow. The code left + (right - left) / 2 gives the same result as (left + right) / 2, but effectively prevents overflow that can occur when left and right are too large and added directly.

1. Finding a Number (Basic Binary Search)

This scenario is the simplest and probably the most familiar to everyone. It involves searching for a number. If the number exists, return its index; otherwise, return -1.

int binarySearch(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;
}

int binarySearch(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;
}

def binarySearch(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

func binarySearch(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 binarySearch = function(nums, target) {
    var left = 0;
    // note
    var right = nums.length - 1;

    while(left <= right) {
        var 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;
    }
};

This code can solve LeetCode problem #704 "Binary Search," but let's delve into the 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: Using the same analysis method, because right = nums.length instead of 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, so it can terminate correctly.

What to Return if target Does Not Exist?

If the value target does not exist in nums, what does the calculated index mean? If I want it to return -1, how should I do it?

// 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;
}

If you want to return -1 when the target does not exist, it's actually quite simple. Just add an extra check when returning to see if nums[left] equals target. If it doesn't, it means the target does not exist. Note that you must ensure the index does not go out of 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
}

Because our update for left must be left = mid + 1, it means that when the while loop ends, nums[left] will definitely not equal target, while nums[left-1] might be target.

As for why the update for left must be left = mid + 1, it is of course to exclude nums[mid] from the search range. We won't elaborate on this here.

What to Return if target Does Not Exist?

If the value target does not exist in nums, what does the calculated index mean? If I want it to return -1, how do I do that?

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

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;
}

So far, we have completed the two implementations of binary search for finding the right boundary. Actually, unifying the "search interval" to be closed on both ends makes it easier to remember, don't you think?

IV. Logical Consistency

With the binary search for both left and right boundaries, you can tackle LeetCode problem #34 "Find First and Last Position of Element in Sorted Array". Let's sort out the causal logic behind these detailed 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:

int binary_search(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) {
            // return directly
            return mid;
        }
    }
    // return directly
    return -1;
}

int left_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) {
            // do not return, lock the left boundary
            right = mid - 1;
        }
    }
    // determine if target exists in nums
    if (left < 0 || left >= nums.length) {
        return -1;
    }
    // check if nums[left] is the target
    return nums[left] == target ? left : -1;
}

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) {
            // do not return, lock the right boundary
            left = mid + 1;
        }
    }
    // since the while loop ends with right == left -
    // 1 and we are now looking for the right boundary
    // it's easier to remember to use right instead of left - 1
    if (right < 0 || right >= nums.length) {
        return -1;
    }
    return nums[right] == target ? right : -1;
}

int binary_search(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) {
            // return directly
            return mid;
        }
    }
    // return directly
    return -1;
}

int left_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) {
            // do not return, lock the left boundary
            right = mid - 1;
        }
    }
    // determine if target exists in nums
    if (left < 0 || left >= nums.size()) {
        return -1;
    }
    // check if nums[left] is target
    return nums[left] == target ? left : -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) {
            // do not return, lock the right boundary
            left = mid + 1;
        }
    }
    // since the while loop ends when right == left
    // - 1, and we are now finding the right
    // so it's easier to remember to use right instead of left - 1
    if (right < 0 || right >= nums.size()) {
        return -1;
    }
    return nums[right] == target ? right : -1;
}

def binary_search(nums: List[int], target: int) -> int:
    # set left and right indexes
    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:
            # found the target value
            return mid
    # target value not found
    return -1

def left_bound(nums: List[int], target: int) -> int:
    # set left and right indexes
    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:
            # target exists, narrow the right boundary
            right = mid - 1
    # determine if the target exists
    if left < 0 or left >= len(nums):
        return -1
    # determine if the left boundary found is the target value
    return left if nums[left] == target else -1

def right_bound(nums: List[int], target: int) -> int:
    # set left and right indexes
    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:
            # target exists, narrow the left boundary
            left = mid + 1
    # determine if the target exists
    if right < 0 or right >= len(nums):
        return -1
    # determine if the right boundary found is the target value
    return right if nums[right] == target else -1

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 {
            left = mid + 1
        } else if nums[mid] > target {
            right = mid - 1
        } else if nums[mid] == target {
            // return directly
            return mid
        }
    }
    // return directly
    return -1
}

func leftBound(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 {
            // do not return, lock the left boundary
            right = mid - 1
        }
    }
    // determine if target exists in nums
    if left < 0 || left >= len(nums) {
        return -1
    }
    // determine if nums[left] is target
    if nums[left] == target {
        return left
    }
    return -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 {
            // do not return, lock the right boundary
            left = mid + 1
        }
    }
    
    if right < 0 || right >= len(nums) {
        return -1
    }
    if nums[right] == target {
        return right
    }
    return -1
}

var binary_search = 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) {
            // return directly
            return mid;
        }
    }
    // return directly
    return -1;
}

var left_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) {
            // do not return, lock the left boundary
            right = mid - 1;
        }
    }
    // determine if target exists in nums
    if (left < 0 || left >= nums.length) {
        return -1;
    }
    // check if nums[left] is the target
    return nums[left] == target ? left : -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) {
            // do not return, lock the right boundary
            left = mid + 1;
        }
    }
    // since the loop ends when right == left - 1 and we are looking for the right boundary
    // so using right instead of left - 1 is easier to remember
    if (right < 0 || right >= nums.length) {
        return -1;
    }
    return nums[right] == target ? right : -1;
}

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.