|
| 1 | +# 二分搜索 |
| 2 | + |
| 3 | +## 简介 |
| 4 | + |
| 5 | +给一个**有序数组**和目标值，找第一次/最后一次/任何一次出现的索引，如果没有出现返回-1 |
| 6 | + |
| 7 | +模板四点要素 |
| 8 | + |
| 9 | +- 1、初始化：start=0、end=len-1 |
| 10 | +- 2、循环退出条件：start + 1 < end |
| 11 | +- 3、比较中点和目标值：A[mid] ==、 <、> target |
| 12 | +- 4、判断最后两个元素是否符合：A[start]、A[end] ? target |
| 13 | + |
| 14 | +时间复杂度 O(logn)，使用场景一般是有序数组的查找 |
| 15 | + |
| 16 | +### 典型示例 |
| 17 | + |
| 18 | +> [704. 二分查找](https://leetcode-cn.com/problems/binary-search/) |
| 19 | +> |
| 20 | +> 给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。 |
| 21 | +
|
| 22 | +```java |
| 23 | +// 二分搜索最常用模板 |
| 24 | +public int search(int[] nums, int target) { |
| 25 | + // 1、初始化left、right |
| 26 | + int left = 0; |
| 27 | + int right = nums.length - 1; |
| 28 | + // 2、处理for循环 |
| 29 | + while (right - left > 1) { |
| 30 | + int mid = left + (right - left) / 2; |
| 31 | + // 3、比较nums[mid]和target值 |
| 32 | + if (nums[mid] == target) { |
| 33 | + return mid; |
| 34 | + } else if (nums[mid] < target) { |
| 35 | + left = mid; |
| 36 | + } else { |
| 37 | + right = mid; |
| 38 | + } |
| 39 | + } |
| 40 | + // 4、最后剩下两个元素，手动判断 |
| 41 | + if (nums[left] == target) { |
| 42 | + return left; |
| 43 | + } else if (nums[right] == target) { |
| 44 | + return right; |
| 45 | + } else { |
| 46 | + return -1; |
| 47 | + } |
| 48 | +} |
| 49 | +``` |
| 50 | + |
| 51 | +### 模板 |
| 52 | + |
| 53 | +大部分二分查找类的题目都可以用这个模板，然后做一点特殊逻辑即可 |
| 54 | + |
| 55 | +另外二分查找还有一些其他模板如下图，大部分场景模板#3 都能解决问题，而且还能找第一次/最后一次出现的位置，应用更加广泛 |
| 56 | + |
| 57 | + |
| 58 | + |
| 59 | +所以用模板#3 就对了，详细的对比可以这边文章介绍：[二分搜索模板](https://leetcode-cn.com/explore/learn/card/binary-search/212/template-analysis/847/) |
| 60 | + |
| 61 | +如果是最简单的二分搜索，不需要找第一个、最后一个位置、或者是没有重复元素，可以使用模板#1，代码更简洁常见题目 |
| 62 | + |
| 63 | +## 常见题目 |
| 64 | + |
| 65 | +### 搜索插入位置 |
| 66 | + |
| 67 | +> [35. 搜索插入位置](https://leetcode-cn.com/problems/search-insert-position/) |
| 68 | +> |
| 69 | +> 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。 |
| 70 | +
|
| 71 | +```java |
| 72 | +public int searchInsert(int[] nums, int target) { |
| 73 | + // 思路：找到第一个 >= target 的元素位置 |
| 74 | + int left = 0; |
| 75 | + int right = nums.length - 1; |
| 76 | + while (right - left > 1) { |
| 77 | + int mid = left + (right - left) / 2; |
| 78 | + if (nums[mid] == target) { |
| 79 | + return mid; |
| 80 | + } else if (nums[mid] < target) { |
| 81 | + left = mid; |
| 82 | + } else { |
| 83 | + right = mid; |
| 84 | + } |
| 85 | + } |
| 86 | + if (nums[left] >= target) { |
| 87 | + return left; |
| 88 | + } else if (nums[left] < target && target <= nums[right]) { |
| 89 | + return left + 1; |
| 90 | + } else { |
| 91 | + // 目标值比所有值都大 |
| 92 | + return right + 1; |
| 93 | + } |
| 94 | +} |
| 95 | +``` |
| 96 | + |
| 97 | +### 搜索二维矩阵 |
| 98 | + |
| 99 | +> [74. 搜索二维矩阵](https://leetcode-cn.com/problems/search-a-2d-matrix/) |
| 100 | +> |
| 101 | +> 编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性： |
| 102 | +> |
| 103 | +> - 每行中的整数从左到右按升序排列。 |
| 104 | +> - 每行的第一个整数大于前一行的最后一个整数。 |
| 105 | +
|
| 106 | +```java |
| 107 | +public boolean searchMatrix(int[][] matrix, int target) { |
| 108 | + // 思路：将2维数组转为1维数组 进行二分搜索 |
| 109 | + if (matrix.length == 0 || matrix[0].length == 0) { |
| 110 | + return false; |
| 111 | + } |
| 112 | + int row = matrix.length; |
| 113 | + int col = matrix[0].length; |
| 114 | + int left = 0; |
| 115 | + int right = row * col - 1; |
| 116 | + while (right - left > 1) { |
| 117 | + int mid = left + (right - left) / 2; |
| 118 | + // 获取2维数组对应值 |
| 119 | + int val = matrix[mid/col][mid%col]; |
| 120 | + if (val < target) { |
| 121 | + left = mid; |
| 122 | + } else if (val > target) { |
| 123 | + right = mid; |
| 124 | + } else { |
| 125 | + return true; |
| 126 | + } |
| 127 | + } |
| 128 | + if (matrix[left/col][left%col] == target || matrix[right/col][right%col] == target) { |
| 129 | + return true; |
| 130 | + } |
| 131 | + return false; |
| 132 | +} |
| 133 | +``` |
| 134 | + |
| 135 | +### 寻找旋转排序数组中的最小值 |
| 136 | + |
| 137 | +> [153. 寻找旋转排序数组中的最小值](https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array/) |
| 138 | +> |
| 139 | +> 假设按照升序排序的数组在预先未知的某个点上进行了旋转( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。 |
| 140 | +> 请找出其中最小的元素。 |
| 141 | +
|
| 142 | +```java |
| 143 | +public int findMin(int[] nums) { |
| 144 | + // 思路：最后一个值作为target，然后往左移动，最后比较start、end的值 |
| 145 | + if (nums.length == 0) { |
| 146 | + return -1; |
| 147 | + } |
| 148 | + int left = 0; |
| 149 | + int right = nums.length - 1; |
| 150 | + while (right - left > 1) { |
| 151 | + int mid = left + (right - left) / 2; |
| 152 | + // 最后一个元素值为target |
| 153 | + if (nums[mid] > nums[right]) { |
| 154 | + left = mid; |
| 155 | + } else { |
| 156 | + right = mid; |
| 157 | + } |
| 158 | + } |
| 159 | + return Math.min(nums[left], nums[right]); |
| 160 | +} |
| 161 | +``` |
| 162 | + |
| 163 | +### 寻找旋转排序数组中的最小值 II |
| 164 | + |
| 165 | +> [154. 寻找旋转排序数组中的最小值 II](https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array-ii/) |
| 166 | +> |
| 167 | +> 假设按照升序排序的数组在预先未知的某个点上进行了旋转 |
| 168 | +> ( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。 |
| 169 | +> 请找出其中最小的元素。(包含重复元素) |
| 170 | +
|
| 171 | +```java |
| 172 | +public int findMin(int[] nums) { |
| 173 | + // 思路：跳过重复元素，mid值和end值比较，分为两种情况进行处理 |
| 174 | + if (nums.length == 0) { |
| 175 | + return -1; |
| 176 | + } |
| 177 | + int left = 0; |
| 178 | + int right = nums.length - 1; |
| 179 | + while (right - left > 1) { |
| 180 | + // 去除重复元素 |
| 181 | + while (left < right && nums[right] == nums[right - 1]) { |
| 182 | + right--; |
| 183 | + } |
| 184 | + while (left < right && nums[left] == nums[left + 1]) { |
| 185 | + left++; |
| 186 | + } |
| 187 | + int mid = left + (right - left) / 2; |
| 188 | + // 中间元素和最后一个元素比较（判断中间点落在左边上升区，还是右边上升区） |
| 189 | + if (nums[mid] > nums[right]) { |
| 190 | + left = mid; |
| 191 | + } else { |
| 192 | + right = mid; |
| 193 | + } |
| 194 | + } |
| 195 | + return Math.min(nums[left], nums[right]); |
| 196 | +} |
| 197 | +``` |
| 198 | + |
| 199 | +### 搜索旋转排序数组 |
| 200 | + |
| 201 | +> [33. 搜索旋转排序数组](https://leetcode-cn.com/problems/search-in-rotated-sorted-array/) |
| 202 | +> |
| 203 | +> 假设按照升序排序的数组在预先未知的某个点上进行了旋转。 |
| 204 | +> ( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。 |
| 205 | +> 搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。 |
| 206 | +> 你可以假设数组中不存在重复的元素。 |
| 207 | +
|
| 208 | +```java |
| 209 | +public int search(int[] nums, int target) { |
| 210 | + // 思路：四种情况判断 |
| 211 | + if (nums.length == 0) { |
| 212 | + return -1; |
| 213 | + } |
| 214 | + int left = 0; |
| 215 | + int right = nums.length - 1; |
| 216 | + while (right - left > 1) { |
| 217 | + int mid = left + (right - left) / 2; |
| 218 | + // 相等直接返回 |
| 219 | + if (nums[mid] == target) { |
| 220 | + return mid; |
| 221 | + } |
| 222 | + // 判断在哪个区间，可能分为四种情况 |
| 223 | + if (nums[left] < nums[mid]) { |
| 224 | + if (nums[left] <= target && target <= nums[mid]) { |
| 225 | + right = mid; |
| 226 | + } else { |
| 227 | + left = mid; |
| 228 | + } |
| 229 | + } else if (nums[right] > nums[mid]) { |
| 230 | + if (nums[right] >= target && target >= nums[mid]) { |
| 231 | + left = mid; |
| 232 | + } else { |
| 233 | + right = mid; |
| 234 | + } |
| 235 | + } |
| 236 | + } |
| 237 | + if (nums[left] == target) { |
| 238 | + return left; |
| 239 | + } else if (nums[right] == target) { |
| 240 | + return right; |
| 241 | + } |
| 242 | + return -1; |
| 243 | +} |
| 244 | +``` |
| 245 | + |
| 246 | +注意点 |
| 247 | + |
| 248 | +> 面试时，可以直接画图进行辅助说明，空讲很容易让大家都比较蒙圈 |
| 249 | +
|
| 250 | +### 搜索旋转排序数组 II |
| 251 | + |
| 252 | +> [81. 搜索旋转排序数组 II](https://leetcode-cn.com/problems/search-in-rotated-sorted-array-ii/) |
| 253 | +> |
| 254 | +> 假设按照升序排序的数组在预先未知的某个点上进行了旋转。 |
| 255 | +> ( 例如，数组 [0,0,1,2,2,5,6] 可能变为 [2,5,6,0,0,1,2] )。 |
| 256 | +> 编写一个函数来判断给定的目标值是否存在于数组中。若存在返回 true，否则返回 false。(包含重复元素) |
| 257 | +
|
| 258 | +```java |
| 259 | +public boolean search(int[] nums, int target) { |
| 260 | + // 思路：四种情况判断 |
| 261 | + if (nums.length == 0) { |
| 262 | + return false; |
| 263 | + } |
| 264 | + int left = 0; |
| 265 | + int right = nums.length - 1; |
| 266 | + while (right - left > 1) { |
| 267 | + // 去除重复元素 |
| 268 | + while (left < right && nums[right] == nums[right - 1]) { |
| 269 | + right--; |
| 270 | + } |
| 271 | + while (left < right && nums[left] == nums[left + 1]) { |
| 272 | + left++; |
| 273 | + } |
| 274 | + int mid = left + (right - left) / 2; |
| 275 | + // 相等直接返回 |
| 276 | + if (nums[mid] == target) { |
| 277 | + return true; |
| 278 | + } |
| 279 | + // 判断在哪个区间，可能分为四种情况 |
| 280 | + if (nums[left] < nums[mid]) { |
| 281 | + if (nums[left] <= target && target <= nums[mid]) { |
| 282 | + right = mid; |
| 283 | + } else { |
| 284 | + left = mid; |
| 285 | + } |
| 286 | + } else if (nums[right] > nums[mid]) { |
| 287 | + if (nums[right] >= target && target >= nums[mid]) { |
| 288 | + left = mid; |
| 289 | + } else { |
| 290 | + right = mid; |
| 291 | + } |
| 292 | + } |
| 293 | + } |
| 294 | + return (nums[left] == target || nums[right] == target); |
| 295 | +} |
| 296 | +``` |
| 297 | + |
| 298 | +## 总结 |
| 299 | + |
| 300 | +二分搜索核心四点要素（必背&理解） |
| 301 | + |
| 302 | +- 1、初始化：start=0、end=len-1 |
| 303 | +- 2、循环退出条件：start + 1 < end |
| 304 | +- 3、比较中点和目标值：A[mid] ==、 <、> target |
| 305 | +- 4、判断最后两个元素是否符合：A[start]、A[end] ? target |
0 commit comments