# 二分搜索算法核心代码模板

Info

**已完成网站教程、网站习题、配套插件中所有多语言代码的校准，解决了之前 chatGPT 翻译可能出错的问题~**

读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：

LeetCode | Difficulty |
---|---|

34. Find First and Last Position of Element in Sorted Array | 🟠 |

704. Binary Search | 🟢 |

Tip

本文有视频版：Core Framework and Techniques of Binary Search。建议关注我的 B 站账号，我会用视频领读的方式带大家学习那些稍有难度的算法技巧。

This article is a revised version of the public account article Binary Search Explained, adding a more detailed analysis of the binary search algorithm.

Let's start with a joke to lighten the mood:

One day, Ah Dong borrowed `N`

books from the library. When 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 pass each book under the alarm to find the one causing the alert, but the guard looked at him disdainfully: "Don't you even know binary search?"

So the guard divided the books into two piles and passed the first pile under the alarm. The alarm sounded, indicating the problematic book was in that pile. He then divided this pile into two more piles and passed the first one under the alarm again. The alarm sounded again, so he continued dividing the pile...

After checking `logN`

times, the guard successfully found the book causing the alarm, with a smug and mocking smile. Ah Dong then left with the remaining books.

From then on, the library was missing `N - 1`

books (手动狗头).

Binary search is not as simple as it seems. Even Knuth, the great mind behind the KMP algorithm, said about binary search: **The idea is straightforward, but the details are the devil.** Many people focus on integer overflow bugs, but the real challenge in binary search is deciding whether to increment or decrement `mid`

, and whether to use `<=`

or `<`

in the while loop.

If you don't correctly understand these details, writing binary search code becomes a mystical process, relying on luck to avoid bugs. Trust me, those who have tried know it. I even wrote a poem to celebrate this algorithm, summarizing the main points of this article. Feel free to save it (wink):

In this article, we will explore 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 inequalities should include equality, and whether `mid`

should be incremented. By analyzing these subtle differences and their causes, you will be able to write accurate and flexible binary search algorithms.

Additionally, I want to clarify that for each binary search scenario, this article will discuss multiple coding approaches. The goal is to help you understand the essence behind these subtle differences, so you won't be confused when you see others' code. In reality, there is no superior or inferior approach; use whatever 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.

相关信息

First, let's address a difference between searching for left and right boundaries and the algorithm mentioned above, which many readers have asked about: **Wasn't the right previously nums.length - 1? Why is it necessary to write it as nums.length here to make the "search interval" left-closed and right-open**?

This writing style is more common for binary search when searching for left and right boundaries, so I used this style as an example to ensure you can understand such code in the future. Using a fully closed interval is actually simpler, and I will provide relevant code later to unify all three types of binary search using a fully closed interval. Just be patient and keep reading.

### 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?

Meaning of `left_bound` Return Value When `target` Does Not Exist

This is a great and important question. Understanding this will prevent confusion in practical applications of binary search.

Straight to the point: **If target does not exist, the binary search for the left boundary returns the smallest index greater than target**.

For example, given `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.

Feeling a bit dizzy? The `left_bound`

function is supposed to search for the left boundary, but when `target`

does not exist, it returns the smallest index greater than `target`

. You don't need to memorize this conclusion. If you're unsure, a simple example can help you derive it.

So, binary search is simple in concept, but the details are tricky. There are many pitfalls. If someone really wants to test you, they can make you doubt your life.

I'm not故意 making the code template complicated; binary search itself is complex. These details are unavoidable. If you haven't grasped these details before, it means your previous learning wasn't solid. Even if you don't use my template, you must understand the behavior of the algorithm when `target`

does not exist. Otherwise, if a bug occurs, you won't know how to fix it—it's that serious.

On the bright side, there's a benefit to this behavior of `left_bound`

. For instance, if you need to write a `floor`

function, you can directly use the `left_bound`

function to implement 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 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 advice is that if you have to write binary search code by hand, you must understand all the behaviors of the code clearly. The framework summarized in this article is designed to help you clarify these details. If it's not necessary, avoid writing it yourself. Instead, use the standard library functions provided by the programming language whenever possible. This can save time, and the behaviors of standard library functions are clearly documented, reducing the chance of errors.

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

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?

Meaning of `right_bound` Return Value When `target` Does Not Exist

To cut to the chase, unlike the previously discussed `left_bound`

: **If target does not exist, the binary search for the right boundary returns the largest index that is less than target**.

You don't need to memorize this conclusion. If you're unsure, a simple example can help you understand. For instance, if `nums = [2,3,5,7]`

and `target = 4`

, the `right_bound`

function returns 1 because the element 3 is the largest element less than 4.

As previously advised, considering the complexity of binary search code details, if not necessary, avoid writing it yourself. Instead, use the standard library functions provided by the programming language whenever possible.

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 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 all the content above, congratulations! The details of the binary search algorithm are just that. Through this article, you have learned:

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.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.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.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.

**引用本文的题目**

**安装 我的 Chrome 刷题插件 点开下列题目可直接查看解题思路：**