Binary Search Algorithm Code Template
This article will resolve
LeetCode | Difficulty |
---|---|
34. Find First and Last Position of Element in Sorted Array | 🟠 |
704. Binary Search | 🟢 |
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 exist
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 exist
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 exist
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 exist
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;
};
Algorithm Visualization
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.
Info
First, let's address a distinction between searching for left and right boundaries and the algorithm mentioned above, which many readers have asked about: Wasn't right
supposed to be nums.length - 1
? Why is it written as nums.length
here to make the "search interval" left-closed and right-open?
This writing style is more common for binary searches involving left and right boundary searches, so I used it as an example to ensure you can understand such code in the future. If you prefer a fully closed interval approach, it's actually simpler. I will provide relevant code later, unifying all three types of binary searches with a fully closed interval approach. Just be patient and continue reading.
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?
Meaning of left_bound
Return Value When target
Does Not Exist
This is an important and excellent question. Understanding this aspect will prevent you from getting confused in real-world applications of binary search.
Here's the conclusion: If target
does not exist, the index returned by the binary search for the left boundary is the smallest index greater than target
.
For example, with nums = [2,3,5,7]
and target = 4
, the left_bound
function returns 2 because the element 5 is the smallest element greater than 4.
A bit confusing, right? The left_bound
function is meant to search for the left boundary, but when target
does not exist, it returns the smallest index greater than target
. There's no need to memorize this; if you're unsure, a simple example can help you arrive at this conclusion.
Binary search might seem straightforward, but the details are intricate and full of pitfalls. If the intention is to test you, there are always ways to challenge your understanding.
The complexity of the binary search code template isn't intentional; binary search itself is inherently complex, and these details cannot be ignored. If you're unfamiliar with these details, it only indicates that your previous learning was not thorough. Even without using the summarized template, you must understand the algorithm's behavior when target
does not exist, or you'll have no idea how to fix bugs, which is indeed serious.
That said, the behavior of left_bound
has an advantage. For instance, if you need to write a floor
function, you can directly implement it using the left_bound
function:
// 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 2.
// Another example, input nums = [1,2,3,5,6], target = 4, the
// function returns 2 because 3 is the largest element less than 4.
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 7
// 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 8
return left_bound(nums, target) - 1;
}
Finally, my suggestion is that if you must write binary search code by hand, you should thoroughly understand the behavior of the code. The framework summarized in this article helps clarify these details. If not necessary, do not write it yourself. Instead, use the standard library functions provided by programming languages whenever possible. This can save time, and the behavior of standard library functions is well-documented, minimizing the chance of errors.
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 downside
// 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 later
// 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;
};
Algorithm Visualization
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?
Meaning of right_bound
Return Value When target
Does Not Exist
To directly state the conclusion, contrary to the left_bound
discussed earlier: If target
does not exist, the binary search for the right boundary returns the largest index smaller than target
.
This conclusion doesn't need to be memorized; if unsure, a simple example can confirm it. For instance, for nums = [2,3,5,7], target = 4
, the right_bound
function returns 1, because the element 3 is the largest element smaller than 4.
As previously advised, considering the complexity of binary search code details, avoid writing it manually if not necessary; use the standard library functions provided by programming languages whenever possible.
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;
};
Algorithm Visualization
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;
}
At this point, the two implementations of binary search for finding the right boundary are complete. In fact, unifying the "search interval" to be closed at both ends is easier to remember, isn't it?
IV. Logical Unification
With the binary search algorithms for both 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 detailed differences:
First, the basic binary search algorithm:
Because we initialize right = nums.length - 1
So our "search interval" is [left, right]
Thus, while (left <= right)
Also, left = mid + 1 and right = mid - 1
Since we only need to find one target index
We can immediately return when nums[mid] == target
Second, binary search for the left boundary:
Because we initialize right = nums.length
So our "search interval" is [left, right)
Thus, while (left < right)
Also, left = mid + 1 and right = mid
Since we need to find the leftmost index of target
Do not return immediately when nums[mid] == target
Instead, tighten the right boundary to lock the left boundary
Third, binary search for the right boundary:
Because we initialize right = nums.length
So our "search interval" is [left, right)
Thus, while (left < right)
Also, left = mid + 1 and right = mid
Since we need to find the rightmost index of target
Do not return immediately when nums[mid] == target
Instead, tighten the left boundary to lock the right boundary
Also, because tightening the left boundary requires left = mid + 1
Finally, whether returning left or right, it must be decremented by one
For binary search that finds the left and right boundaries, a common technique is to use a "search interval" that is left-closed and right-open. We have unified the "search interval" to be closed at both ends for easier memorization. By modifying two places, three different writing styles can be achieved:
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 boundary
// 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 the above content, congratulations, the details of the binary search algorithm are just so. Through this article, you have learned:
When analyzing binary search code, avoid using else; expand all into else if for easier understanding. Once the logic is correct, merge branches to enhance efficiency.
Pay attention to the "search interval" and the termination condition of while; if there are missing elements, remember to check at the end.
If you need to define a left-closed and right-open "search interval" to search for left and right boundaries, just modify when
nums[mid] == target
. For searching the right side, subtract one.If you unify the "search interval" to be closed at both ends, it's easy to remember. Just slightly modify the code at the
nums[mid] == target
condition and the return logic. It's recommended to note this down as a binary search template.
Finally, I would like to say, the above framework of binary search belongs to the category of "techniques." If elevated to the level of "principle," the essence of binary thinking is: to reduce (halve) the search space as much as possible through known information, thereby increasing the efficiency of brute-force search to quickly find the target.
Understanding this article can ensure you write correct binary search code, but in real 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 In Real World and More Binary Search Exercises.
Related Problems
You can install my Chrome extension then open the link.