Java二分查找之循環(huán)條件與區(qū)間寫法詳解
更新時(shí)間：2026年03月17日 09:37:32 作者：識(shí)君啊
二分查找算法是一種高效的搜索算法,適用于有序數(shù)組,它通過將查找范圍不斷減半,逐步縮小目標(biāo)值的搜索空間,最終找到目標(biāo)元素或確認(rèn)目標(biāo)不存在,這篇文章主要介紹了Java二分查找之循環(huán)條件與區(qū)間寫法的相關(guān)資料,需要的朋友可以參考下
二分查找：每次排除一半，log n 解決問題
一、核心概念
1.1 什么是二分查找？
本質(zhì)： 在有序數(shù)組中，每次取中間元素比較，根據(jù)結(jié)果排除一半元素。
前提： 數(shù)組必須有序
復(fù)雜度： O(log n)
直觀對(duì)比：
線性查找100萬個(gè)數(shù)：最多100萬次 二分查找100萬個(gè)數(shù)：最多20次（log?1000000 ≈ 20）
示例：
數(shù)組：[1, 3, 5, 7, 9, 11, 13, 15] 查找：11 第1次：mid=7，11>7，搜索右半邊 第2次：mid=11，找到！
二、基礎(chǔ)模板
2.1 標(biāo)準(zhǔn)二分查找
LeetCode 704： 在有序數(shù)組中查找目標(biāo)值，返回索引，不存在返回-1。
代碼：
public int binarySearch(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2; // 防溢出
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
left = mid + 1; // 搜索右半邊
} else {
right = mid - 1; // 搜索左半邊
}
}
return -1;
}
關(guān)鍵細(xì)節(jié)：
防溢出：
mid = left + (right - left) / 2// 錯(cuò)誤：left + right 可能溢出 int mid = (left + right) / 2; // 正確：不會(huì)溢出 int mid = left + (right - left) / 2;
循環(huán)條件：
while (left <= right)vswhile (left < right)// left <= right：適用于查找具體值 // 區(qū)間 [left, right]，閉區(qū)間，包含兩端 // 當(dāng) left == right 時(shí)，還有1個(gè)元素要檢查 // left < right：適用于縮小范圍找唯一解 // 區(qū)間 [left, right]，但循環(huán)結(jié)束時(shí) left == right // 常用于找邊界、找峰值等問題
邊界更新：
left = mid + 1和right = mid - 1// nums[mid] 已檢查過，不是目標(biāo)值 // 所以下次搜索要排除 mid
2.2 查找左邊界
問題： 在有序數(shù)組中查找第一個(gè)等于 target 的位置。
示例： nums = [1,2,2,2,3], target = 2 → 返回 1
思路： 即使找到 target，也繼續(xù)向左搜索。
代碼（閉區(qū)間寫法）：
public int searchLeft(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 {
// 關(guān)鍵：即使 nums[mid] == target，也繼續(xù)向左
right = mid - 1;
}
}
// 檢查 left 是否越界，以及是否等于 target
if (left >= nums.length || nums[left] != target) {
return -1;
}
return left;
}
代碼（左閉右開寫法）：
public int searchLeft(int[] nums, int target) {
int left = 0, right = nums.length; // 注意：right = length
while (left < right) { // 注意：left < right
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid; // 注意：right = mid，不是 mid - 1
}
}
// 檢查邊界
if (left >= nums.length || nums[left] != target) {
return -1;
}
return left;
}
推導(dǎo)過程：
數(shù)組：[1, 2, 2, 2, 3]，查找 2 的左邊界 初始：left=0, right=4 第1輪：mid=2, nums[2]=2 >= 2, right=1 第2輪：mid=0, nums[0]=1 < 2, left=1 第3輪：left=1, right=1, mid=1, nums[1]=2 >= 2, right=0 第4輪：left > right，退出 返回 left=1
2.3 查找右邊界
問題： 在有序數(shù)組中查找最后一個(gè)等于 target 的位置。
示例： nums = [1,2,2,2,3], target = 2 → 返回 3
代碼（閉區(qū)間寫法）：
public int searchRight(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] <= target) {
// 關(guān)鍵：即使 nums[mid] == target，也繼續(xù)向右
left = mid + 1;
} else {
right = mid - 1;
}
}
// 檢查 right 是否越界，以及是否等于 target
if (right < 0 || nums[right] != target) {
return -1;
}
return right;
}
代碼（左閉右開寫法）：
public int searchRight(int[] nums, int target) {
int left = 0, right = nums.length;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] <= target) {
left = mid + 1;
} else {
right = mid;
}
}
// 注意：返回 left - 1
if (left - 1 < 0 || nums[left - 1] != target) {
return -1;
}
return left - 1;
}
2.4 查找插入位置
LeetCode 35： 在有序數(shù)組中查找 target 的插入位置（保持有序）。
示例： nums = [1,3,5,7], target = 4 → 返回 2
代碼：
public int searchInsert(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 {
right = mid - 1;
}
}
// 循環(huán)結(jié)束時(shí)，left 就是插入位置
return left;
}
三、經(jīng)典題目
3.1 搜索旋轉(zhuǎn)排序數(shù)組（LeetCode 33）
題目： 在旋轉(zhuǎn)后的有序數(shù)組中查找目標(biāo)值。
示例： nums = [4,5,6,7,0,1,2], target = 0 → 返回 4
思路： 數(shù)組被旋轉(zhuǎn)后，至少有一半是有序的，判斷 target 在哪一半。
代碼：
public int 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) return mid;
// 判斷哪一半是有序的
if (nums[left] <= nums[mid]) {
// 左半邊有序 [left, mid]
if (nums[left] <= target && target < nums[mid]) {
right = mid - 1; // target 在左半邊
} else {
left = mid + 1; // target 在右半邊
}
} else {
// 右半邊有序 [mid, right]
if (nums[mid] < target && target <= nums[right]) {
left = mid + 1; // target 在右半邊
} else {
right = mid - 1; // target 在左半邊
}
}
}
return -1;
}
3.2 在排序數(shù)組中查找元素的第一個(gè)和最后一個(gè)位置（LeetCode 34）
題目： 找到 target 的左右邊界。
示例： nums = [5,7,7,8,8,10], target = 8 → 返回 [3,4]
代碼：
public int[] searchRange(int[] nums, int target) {
int left = searchLeft(nums, target);
int right = searchRight(nums, target);
return new int[]{left, right};
}
// 使用前面的 searchLeft 和 searchRight 方法
3.3 尋找峰值（LeetCode 162）
題目： 找到數(shù)組中的峰值（比相鄰元素都大）。
示例： nums = [1,2,3,1] → 返回 2
思路： 如果 nums[mid] < nums[mid+1]，峰值一定在右邊。
代碼：
public int findPeakElement(int[] nums) {
int left = 0, right = nums.length - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] < nums[mid + 1]) {
left = mid + 1; // 峰值在右邊
} else {
right = mid; // 峰值在左邊或就是 mid
}
}
return left;
}
3.4 搜索二維矩陣（LeetCode 74）
題目： 在二維矩陣中查找目標(biāo)值（每行有序，每行第一個(gè)元素大于上一行最后一個(gè)）。
思路： 把二維矩陣看成一維數(shù)組，用二分查找。
代碼：
public boolean searchMatrix(int[][] matrix, int target) {
int m = matrix.length, n = matrix[0].length;
int left = 0, right = m * n - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
// 將一維索引轉(zhuǎn)換為二維坐標(biāo)
int row = mid / n;
int col = mid % n;
int num = matrix[row][col];
if (num == target) {
return true;
} else if (num < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return false;
}
3.5 尋找旋轉(zhuǎn)排序數(shù)組中的最小值（LeetCode 153）
題目： 找到旋轉(zhuǎn)后數(shù)組的最小值。
示例： nums = [3,4,5,1,2] → 返回 1
代碼：
public int findMin(int[] nums) {
int left = 0, right = nums.length - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] > nums[right]) {
left = mid + 1; // 最小值在右邊
} else {
right = mid; // 最小值在左邊或就是 mid
}
}
return nums[left];
}
四、進(jìn)階技巧
4.1 二分答案
核心思想： 當(dāng)問題的答案具有單調(diào)性時(shí)，可以二分答案，然后驗(yàn)證。
適用場景：
- 求"最大值的最小"或"最小值的最大"
- 答案在某個(gè)范圍內(nèi)，且具有單調(diào)性
例題1：分割數(shù)組的最大值（LeetCode 410）
題目： 將數(shù)組分成 m 個(gè)非空連續(xù)子數(shù)組，使這 m 個(gè)子數(shù)組各自和的最大值最小。
示例：
輸入：nums = [7,2,5,10,8], m = 2 輸出：18 解釋：分成 [7,2,5] 和 [10,8]，最大和為 18
思路：
- 答案范圍：[max(nums), sum(nums)]
- 二分答案 mid，檢查能否在 mid 限制下分成 m 個(gè)子數(shù)組
- 如果可以，說明答案可能更小，right = mid - 1
- 如果不行，說明答案太小，left = mid + 1
代碼：
public int splitArray(int[] nums, int m) {
int left = 0, right = 0;
// 確定答案范圍
for (int num : nums) {
left = Math.max(left, num); // 最小可能：數(shù)組最大值
right += num; // 最大可能：數(shù)組總和
}
// 二分答案
while (left <= right) {
int mid = left + (right - left) / 2;
if (canSplit(nums, m, mid)) {
right = mid - 1; // 可以分，嘗試更小的答案
} else {
left = mid + 1; // 不能分，答案太小
}
}
return left;
}
// 檢查能否在 maxSum 限制下分成 m 個(gè)子數(shù)組
private boolean canSplit(int[] nums, int m, int maxSum) {
int count = 1; // 至少需要1個(gè)子數(shù)組
int sum = 0;
for (int num : nums) {
if (sum + num > maxSum) {
count++; // 需要新的子數(shù)組
sum = num;
} else {
sum += num;
}
}
return count <= m;
}
時(shí)間復(fù)雜度： O(n × log(sum))
例題2：在 D 天內(nèi)送達(dá)包裹的能力（LeetCode 1011）
題目： 傳送帶上的包裹必須在 D 天內(nèi)送達(dá)，求傳送帶的最低運(yùn)載能力。
示例：
輸入：weights = [1,2,3,4,5,6,7,8,9,10], D = 5 輸出：15 解釋：每天運(yùn)載能力為 15，可以在 5 天內(nèi)送完
代碼：
public int shipWithinDays(int[] weights, int days) {
int left = 0, right = 0;
for (int w : weights) {
left = Math.max(left, w); // 最小運(yùn)載能力：最重的包裹
right += w; // 最大運(yùn)載能力：所有包裹總重
}
while (left <= right) {
int mid = left + (right - left) / 2;
if (canShip(weights, days, mid)) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return left;
}
private boolean canShip(int[] weights, int days, int capacity) {
int needDays = 1, load = 0;
for (int w : weights) {
if (load + w > capacity) {
needDays++;
load = w;
} else {
load += w;
}
}
return needDays <= days;
}
4.2 區(qū)間寫法對(duì)比
二分查找有兩種常見的區(qū)間寫法，各有優(yōu)劣。
閉區(qū)間 [left, right]
特點(diǎn)：
right = nums.length - 1while (left <= right)right = mid - 1或left = mid + 1
優(yōu)點(diǎn)：
- 直觀，容易理解
- 邊界條件清晰
- 適合查找具體值
缺點(diǎn)：
- 需要注意
<=和-1 - 容易寫錯(cuò)邊界更新
示例：
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
左閉右開 [left, right)
特點(diǎn)：
right = nums.lengthwhile (left < right)right = mid或left = mid + 1
優(yōu)點(diǎn)：
- 不容易死循環(huán)
- 適合找邊界、找峰值
- 循環(huán)結(jié)束時(shí)
left == right
缺點(diǎn)：
- 不夠直觀
- 返回值需要注意（可能是
left - 1）
示例：
int left = 0, right = nums.length;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid; // 注意：不是 mid - 1
}
}
return left; // 或 left - 1，取決于具體問題
如何選擇？
| 場景 | 推薦寫法 | 原因 |
|---|---|---|
| 查找具體值 | 閉區(qū)間 | 直觀，容易理解 |
| 查找左邊界 | 兩種都可以 | 閉區(qū)間更常見 |
| 查找右邊界 | 兩種都可以 | 閉區(qū)間更常見 |
| 找峰值、最小值 | 左閉右開 | 不容易死循環(huán) |
| 二分答案 | 閉區(qū)間 | 邊界條件清晰 |
建議：
- 初學(xué)者：統(tǒng)一用閉區(qū)間，容易理解
- 熟練后：根據(jù)場景選擇，左閉右開在某些題目中更簡潔
4.3 循環(huán)條件詳解
while (left <= right) vs while (left < right)
這是二分查找中最容易混淆的點(diǎn)，理解它們的區(qū)別非常重要。
while (left <= right)- 查找具體值
適用場景： 查找數(shù)組中是否存在某個(gè)具體值
特點(diǎn)：
- 區(qū)間 [left, right]，閉區(qū)間
- 當(dāng)
left == right時(shí)，還有1個(gè)元素要檢查 - 循環(huán)結(jié)束時(shí)，
left > right
示例：
// 查找 target 是否存在
int left = 0, right = nums.length - 1;
while (left <= right) { // 包含 left == right 的情況
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid; // 找到了
} else if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1; // 沒找到
為什么用 <=？
假設(shè) nums = [5], target = 5 初始：left = 0, right = 0 如果用 left < right： 循環(huán)不執(zhí)行，直接返回 -1（錯(cuò)誤?。? 如果用 left <= right： 第1輪：left = 0, right = 0, mid = 0 nums[0] = 5 == target，返回 0（正確?。?
while (left < right)- 縮小范圍找唯一解
適用場景： 縮小范圍直到找到唯一解（邊界、峰值、最小值等）
特點(diǎn)：
- 循環(huán)結(jié)束時(shí)，
left == right，指向唯一解 - 不需要判斷
nums[mid] == target - 常用于找邊界、找峰值
示例1：尋找峰值
int left = 0, right = nums.length - 1;
while (left < right) { // 縮小范圍
int mid = left + (right - left) / 2;
if (nums[mid] < nums[mid + 1]) {
left = mid + 1; // 峰值在右邊
} else {
right = mid; // 峰值在左邊或就是 mid
}
}
return left; // left == right，指向峰值
示例2：尋找旋轉(zhuǎn)數(shù)組最小值
int left = 0, right = nums.length - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] > nums[right]) {
left = mid + 1; // 最小值在右邊
} else {
right = mid; // 最小值在左邊或就是 mid
}
}
return nums[left]; // left == right，指向最小值
為什么用 <？
因?yàn)槲覀儾皇窃谡揖唧w值，而是在縮小范圍 循環(huán)結(jié)束時(shí)： left == right，指向唯一解 如果用 left <= right： 可能會(huì)死循環(huán)（當(dāng) right = mid 時(shí)）
對(duì)比總結(jié)
| 對(duì)比項(xiàng) | left <= right | left < right |
|---|---|---|
| 適用場景 | 查找具體值 | 縮小范圍找唯一解 |
| 循環(huán)結(jié)束條件 | left > right | left == right |
| 是否需要判斷相等 | 需要 | 不需要 |
| 邊界更新 | right = mid - 1 | right = mid |
| 典型題目 | 二分查找、查找插入位置 | 尋找峰值、旋轉(zhuǎn)數(shù)組最小值 |
記憶技巧：
left <= right：找具體值，要檢查所有元素 left < right：找范圍，縮小到唯一解
4.4 第 K 小/大元素
核心： 二分答案，統(tǒng)計(jì)小于等于 mid 的元素個(gè)數(shù)。
例題：有序矩陣中第 K 小的元素（LeetCode 378）
題目： 在 n×n 矩陣中（每行每列都升序），找第 k 小的元素。
示例：
matrix = [ [1, 5, 9], [10, 11, 13], [12, 13, 15] ] k = 8 輸出：13
思路： 二分答案，統(tǒng)計(jì)矩陣中小于等于 mid 的元素個(gè)數(shù)。
代碼：
public int kthSmallest(int[][] matrix, int k) {
int n = matrix.length;
int left = matrix[0][0];
int right = matrix[n-1][n-1];
while (left < right) {
int mid = left + (right - left) / 2;
int count = countLessEqual(matrix, mid);
if (count < k) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}
// 統(tǒng)計(jì)矩陣中小于等于 target 的元素個(gè)數(shù)
private int countLessEqual(int[][] matrix, int target) {
int n = matrix.length;
int count = 0;
int row = n - 1, col = 0; // 從左下角開始
while (row >= 0 && col < n) {
if (matrix[row][col] <= target) {
count += row + 1; // 這一列前 row+1 個(gè)元素都 <= target
col++;
} else {
row--;
}
}
return count;
}
時(shí)間復(fù)雜度： O(n × log(max - min))
4.5 最小化最大值/最大化最小值
這類問題的特征：
- 求"最大值的最小"
- 求"最小值的最大"
- 答案具有單調(diào)性
通用思路：
- 確定答案范圍 [left, right]
- 二分答案 mid
- 檢查 mid 是否滿足條件
- 根據(jù)結(jié)果調(diào)整范圍
例題：磁力石（LeetCode 1552）
題目： 在 position 數(shù)組中選 m 個(gè)位置放球，使任意兩球間的最小磁力最大。
示例：
輸入：position = [1,2,3,4,7], m = 3 輸出：3 解釋：放在 1, 4, 7，最小距離為 3
代碼：
public int maxDistance(int[] position, int m) {
Arrays.sort(position);
int left = 1;
int right = position[position.length - 1] - position[0];
while (left <= right) {
int mid = left + (right - left) / 2;
if (canPlace(position, m, mid)) {
left = mid + 1; // 可以放，嘗試更大的距離
} else {
right = mid - 1; // 不能放，距離太大
}
}
return right;
}
// 檢查能否以 minDist 的最小距離放 m 個(gè)球
private boolean canPlace(int[] position, int m, int minDist) {
int count = 1; // 第一個(gè)位置必放
int lastPos = position[0];
for (int i = 1; i < position.length; i++) {
if (position[i] - lastPos >= minDist) {
count++;
lastPos = position[i];
}
}
return count >= m;
}
五、通用模板總結(jié)
模板1：標(biāo)準(zhǔn)二分查找（閉區(qū)間）
int left = 0, right = nums.length - 1;
while (left <= right) { // 注意：<=
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1; // 注意：mid - 1
}
}
return -1;
模板2：查找左邊界（閉區(qū)間）
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return (left < nums.length && nums[left] == target) ? left : -1;
模板3：查找右邊界（閉區(qū)間）
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] <= target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return (right >= 0 && nums[right] == target) ? right : -1;
模板4：縮小范圍找唯一解（左閉右開）
int left = 0, right = nums.length; // 注意：right = length
while (left < right) { // 注意：<
int mid = left + (right - left) / 2;
if (check(mid)) {
right = mid; // 注意：mid，不是 mid - 1
} else {
left = mid + 1;
}
}
return left; // left == right
模板5：二分答案
int left = minAnswer, right = maxAnswer;
while (left <= right) {
int mid = left + (right - left) / 2;
if (check(mid)) {
right = mid - 1; // 答案可能更小
} else {
left = mid + 1; // 答案太小
}
}
return left;
六、常見錯(cuò)誤與避坑
錯(cuò)誤1：死循環(huán)
// 錯(cuò)誤：使用 left < right，但更新時(shí)用 left = mid
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid; // 當(dāng) left=mid 時(shí)會(huì)死循環(huán)
} else {
right = mid - 1;
}
}
// 正確：要么用 left <= right + left = mid + 1
// 要么用 left < right + right = mid
錯(cuò)誤2：邊界檢查遺漏
// 錯(cuò)誤：返回前沒有檢查邊界
return left; // left 可能越界
// 正確：檢查邊界
if (left >= nums.length || nums[left] != target) {
return -1;
}
return left;
錯(cuò)誤3：整數(shù)溢出
// 錯(cuò)誤：left + right 可能溢出 int mid = (left + right) / 2; // 正確：不會(huì)溢出 int mid = left + (right - left) / 2;
錯(cuò)誤4：循環(huán)條件與邊界更新不匹配
// 錯(cuò)誤：用 left < right，但更新時(shí)用 right = mid - 1
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1; // 錯(cuò)誤！應(yīng)該是 right = mid
}
}
// 正確：left < right 配合 right = mid
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid; // 正確
}
}
錯(cuò)誤5：混淆閉區(qū)間和左閉右開
// 錯(cuò)誤：初始化用 length - 1，但循環(huán)用 left < right
int left = 0, right = nums.length - 1; // 閉區(qū)間
while (left < right) { // 左閉右開的循環(huán)條件
// ...
}
// 正確：統(tǒng)一使用閉區(qū)間
int left = 0, right = nums.length - 1;
while (left <= right) {
// ...
}
// 或統(tǒng)一使用左閉右開
int left = 0, right = nums.length;
while (left < right) {
// ...
}
七、題目推薦
| 題號(hào) | 題目 | 難度 | 類型 |
|---|---|---|---|
| 704 | 二分查找 | 簡單 | 標(biāo)準(zhǔn)模板 |
| 35 | 搜索插入位置 | 簡單 | 插入位置 |
| 34 | 在排序數(shù)組中查找元素的第一個(gè)和最后一個(gè)位置 | 中等 | 左右邊界 |
| 33 | 搜索旋轉(zhuǎn)排序數(shù)組 | 中等 | 旋轉(zhuǎn)數(shù)組 |
| 81 | 搜索旋轉(zhuǎn)排序數(shù)組II | 中等 | 旋轉(zhuǎn)數(shù)組+重復(fù) |
| 153 | 尋找旋轉(zhuǎn)排序數(shù)組中的最小值 | 中等 | 旋轉(zhuǎn)數(shù)組 |
| 154 | 尋找旋轉(zhuǎn)排序數(shù)組中的最小值II | 困難 | 旋轉(zhuǎn)數(shù)組+重復(fù) |
| 162 | 尋找峰值 | 中等 | 峰值 |
| 74 | 搜索二維矩陣 | 中等 | 二維轉(zhuǎn)一維 |
| 240 | 搜索二維矩陣II | 中等 | 從右上角開始 |
| 410 | 分割數(shù)組的最大值 | 困難 | 二分答案 |
| 1011 | 在D天內(nèi)送達(dá)包裹的能力 | 中等 | 二分答案 |
| 875 | 愛吃香蕉的珂珂 | 中等 | 二分答案 |
| 1552 | 兩球之間的磁力 | 中等 | 最大化最小值 |
| 378 | 有序矩陣中第K小的元素 | 中等 | 第K小 |
| 69 | x的平方根 | 簡單 | 整數(shù)二分 |
八、總結(jié)
核心要點(diǎn)
二分查找 = 每次排除一半
- 時(shí)間復(fù)雜度：O(log n)
- 前提：數(shù)組有序
循環(huán)條件的選擇（重要?。?/strong>
left <= right：查找具體值，檢查所有元素left < right：縮小范圍找唯一解，循環(huán)結(jié)束時(shí) left == right
區(qū)間寫法的選擇
- 閉區(qū)間 [left, right]：直觀，適合查找具體值
- 左閉右開 [left, right)：不易死循環(huán)，適合找邊界
三種基礎(chǔ)模板
- 標(biāo)準(zhǔn)二分：查找目標(biāo)值
- 左邊界：查找第一個(gè)等于 target 的位置
- 右邊界：查找最后一個(gè)等于 target 的位置
進(jìn)階技巧
- 二分答案：答案具有單調(diào)性
- 第 K 小/大：二分答案 + 統(tǒng)計(jì)
- 最大化最小值/最小化最大值
關(guān)鍵細(xì)節(jié)
mid = left + (right - left) / 2（防溢出）- 循環(huán)條件與邊界更新要匹配
- 注意邊界檢查，避免越界
學(xué)習(xí)建議
理解循環(huán)條件的本質(zhì)
left <= right：查找具體值left < right：縮小范圍- 這是二分查找最重要的知識(shí)點(diǎn)
選擇一種區(qū)間寫法并堅(jiān)持
- 初學(xué)者：統(tǒng)一用閉區(qū)間 [left, right]
- 熟練后：根據(jù)場景靈活選擇
刷題順序
- 先刷 LeetCode 704（標(biāo)準(zhǔn)二分）
- 再刷 LeetCode 34（左右邊界）
- 然后刷 LeetCode 162、153（縮小范圍）
- 最后刷 LeetCode 410、1011（二分答案）
多畫圖理解
- 每次循環(huán)畫出 left、mid、right
- 理解為什么這樣更新邊界
- 理解循環(huán)結(jié)束時(shí)的狀態(tài)
總結(jié)
到此這篇關(guān)于Java二分查找之循環(huán)條件與區(qū)間寫法詳解的文章就介紹到這了,更多相關(guān)Java二分查找循環(huán)條件與區(qū)間內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
這篇文章主要介紹了使用maven打包生成doc文檔和打包源碼的實(shí)現(xiàn)，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2021-07-07
解決MultipartFile.transferTo(dest) 報(bào)FileNotFoundExcep的問題
這篇文章主要介紹了解決MultipartFile.transferTo(dest) 報(bào)FileNotFoundExcep的問題，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2021-07-07
這篇文章主要為大家詳細(xì)介紹了Java集合中的Map接口與實(shí)現(xiàn)類，文中的示例代碼講解詳細(xì)，對(duì)我們學(xué)習(xí)Java有一定的幫助，感興趣的可以了解一下2022-12-12
Java數(shù)據(jù)結(jié)構(gòu)之棧的基本定義與實(shí)現(xiàn)方法示例
這篇文章主要介紹了Java數(shù)據(jù)結(jié)構(gòu)之棧的基本定義與實(shí)現(xiàn)方法,簡單描述了數(shù)據(jù)結(jié)構(gòu)中棧的功能、原理,并結(jié)合java實(shí)例形式分析了棧的基本定義與使用方法,需要的朋友可以參考下2017-10-10
Java Web實(shí)現(xiàn)文件下載和亂碼處理方法
文件上傳和下載是web開發(fā)中常遇到的問題。今天小編給大家分享下Java Web實(shí)現(xiàn)文件下載和亂碼處理方法的相關(guān)資料,需要的朋友可以參考下2016-10-10
這篇文章主要介紹了Java的LinkedHashSet源碼深入講解,LinkedHashSet是HashSet的子類,而由于HashSet實(shí)現(xiàn)了Set接口,因此LinkedHashSet也間接實(shí)現(xiàn)了Set類,LinkedHashSet類屬于java.base模塊,java.util包下,需要的朋友可以參考下2023-09-09
基于SpringBoot和Leaflet的行政區(qū)劃地圖掩膜效果實(shí)戰(zhàn)教程
本文講解的是一種圖層級(jí)的掩膜,即使用行政區(qū)劃圖層來進(jìn)行掩膜,使用場景為,用戶只需要在地圖頁面中展示目標(biāo)行政區(qū)劃內(nèi)的影像信息,對(duì)于行政邊界外的影像,這篇文章主要介紹了基于SpringBoot和Leaflet的行政區(qū)劃地圖掩膜效果實(shí)戰(zhàn),需要的朋友可以參考下2024-05-05
JUC中的wait與notify方法實(shí)現(xiàn)原理詳解
這篇文章主要介紹了JUC中的wait與notify方法實(shí)現(xiàn)原理，在進(jìn)行wait()之前，就代表著需要爭奪Synchorized，而Synchronized代碼塊通過javap生成的字節(jié)碼中包含monitor?enter和monitor?exit兩個(gè)指令2023-03-03
本篇文章主要介紹了Spring-Boot框架初步搭建，小編覺得挺不錯(cuò)的，現(xiàn)在分享給大家，也給大家做個(gè)參考。一起跟隨小編過來看看吧2017-03-03
Mybatis中關(guān)于自定義mapper.xml時(shí),參數(shù)傳遞的方式及寫法
這篇文章主要介紹了Mybatis中關(guān)于自定義mapper.xml時(shí),參數(shù)傳遞的方式及寫法,具有很好的參考價(jià)值,希望對(duì)大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2023-12-12