给一个有序数组和目标值，找第一次/最后一次/任何一次出现的索引，如果没有出现返回-1
模板四点要素
- 1、初始化：start=0、end=len-1
- 2、循环条件：start <= end
- 3、比较中点和目标值：A[mid] ==、 <、> target
- 4、判断最后两个元素是否符合：A[start]、A[end] ? target
时间复杂度 O(logn)，使用场景一般是有序数组的查找
典型示例
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
// 二分搜索最常用模板
class Solution {
public int search(int[] nums, int target) {
int mid, left = 0, right = nums.length - 1;
// 处理for循环
while (left + 1 < right) {
mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
// 最后剩下两个元素，手动判断
if (nums[left] == target) {
return left;
}
if (nums[right] == target) {
return right;
}
return -1;
}
}大部分二分查找类的题目都可以用这个模板，然后做一点特殊逻辑即可
另外二分查找还有一些其他模板如下图，大部分场景模板#3 都能解决问题，而且还能找第一次/最后一次出现的位置，应用更加广泛
所以用模板#3 就对了，详细的对比可以这边文章介绍：二分搜索模板
如果是最简单的二分搜索，不需要找第一个、最后一个位置、或者是没有重复元素，可以使用模板#1，代码更简洁
// 无重复元素搜索时，更方便
class Solution {
public int search(int[] nums, int target) {
int mid, left = 0, right = nums.length - 1;
while (left <= right) {
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;
}
}给定一个包含 n 个整数的排序数组，找出给定目标值 target 的起始和结束位置。 如果目标值不在数组中，则返回
[-1, -1]
思路：用二分查找，找到第一次出现target的位置，然后往下遍历找到第二次出现target的位置
class Solution {
public int[] searchRange(int[] nums, int target) {
int[] ans = new int[]{-1, -1};
if (nums.length == 0 || nums[0] > target) {
return ans;
}
int low = 0, high = nums.length - 1;
// 用二分查找，找到第一次出现target的位置
while (low <= high) {
int mid = low + ((high - low) >> 1);
if (nums[mid] >= target) {
if (mid == 0 || (nums[mid] == target && nums[mid - 1] < target)) {
ans[0] = mid;
break;
}
else {
high = mid - 1;
}
}
else {
low = mid + 1;
}
}
if (ans[0] != -1 && nums[ans[0]] == target) {
if (ans[0] == nums.length - 1) {
ans[1] = ans[0];
}
else {
// 往下遍历找到第二次出现target 的位置
for (int i = ans[0] + 1; i < nums.length; ++i) {
if (nums[i] != target) {
ans[1] = i - 1;
break;
}
if (i == nums.length - 1 && nums[i] == target) {
ans[1] = i;
}
}
}
}
return ans;
}
}给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
class Solution {
public int searchInsert(int[] nums, int target) {
int left = 0, right = nums.length;
if (right == 0) {
return 0;
}
while (left < right) {
int mid = left + ((right - left) >>> 1);
if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid;
} else {
return mid;
}
}
return left;
}
}编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：
- 每行中的整数从左到右按升序排列。
- 每行的第一个整数大于前一行的最后一个整数。
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int m = matrix.length;
if (m == 0) {
return false;
}
int n = matrix[0].length;
int left = 0, right = m * n - 1;
int index, value;
while (left <= right) {
index = left + ((right - left) >>> 1);
value = matrix[index / n][index % n];
if (value == target) {
return true;
} else if (value < target) {
left = index + 1;
} else {
right = index - 1;
}
}
return false;
}
}假设你有 n 个版本 [1, 2, ..., n]，你想找出导致之后所有版本出错的第一个错误的版本。 你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。
/* The isBadVersion API is defined in the parent class VersionControl.
boolean isBadVersion(int version); */
public class Solution extends VersionControl {
public int firstBadVersion(int n) {
int left = 0, right = n;
while (left < right) {
int mid = left + ((right - left) >> 1);
if (isBadVersion(mid)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
}假设按照升序排序的数组在预先未知的某个点上进行了旋转( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。 请找出其中最小的元素。
经我测试这道题不用二分查找反而更快，找到第一个比前一个值小的数就是最小值
class Solution {
public int findMin(int[] nums) {
int len = nums.length;
if(len == 1) {
return nums[0];
}
for(int i = 1; i < len; ++i) {
if(nums[i] < nums[i-1]) {
return nums[i];
}
}
return nums[0];
}
}假设按照升序排序的数组在预先未知的某个点上进行了旋转 ( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。 请找出其中最小的元素。(包含重复元素)
class Solution {
public int findMin(int[] nums) {
int right = nums.length - 1, left = 0;
if(right == 0) {
return nums[0];
}
// 把nums[right]当做target做二分
while (left < right) {
int mid = left + ((right - left) >> 1);
if (nums[mid] < nums[right]) {
right = mid;
} else if (nums[mid] > nums[right]) { //最小值一定在[mid+1, right]索引中
left = mid + 1;
} else { // 相等表示重复，往左边移一位
right--;
}
}
return nums[left];
}
}假设按照升序排序的数组在预先未知的某个点上进行了旋转。 ( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。 搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。 你可以假设数组中不存在重复的元素。
class Solution {
public int search(int[] nums, int target) {
int left = 0, len = nums.length, right = len - 1;
if (len == 0) {
return -1;
}
if (len == 1) {
return nums[0] == target ? 0 : -1;
}
while (left <= right) {
int mid = left + ((right - left) >> 1);
if (nums[mid] == target) {
return mid;
}
// 左半段
if (nums[0] <= nums[mid]) {
// 左半段左部
if (nums[0] <= target && target < nums[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
} else { // 右半段
// 右半段右部
if (target > nums[mid] && target <= nums[len - 1]) {
left = mid + 1;
} else {
right = mid - 1;
}
}
}
return -1;
}
}注意点
面试时，可以直接画图进行辅助说明，空讲很容易让大家都比较蒙圈
假设按照升序排序的数组在预先未知的某个点上进行了旋转。 ( 例如，数组 [0,0,1,2,2,5,6] 可能变为 [2,5,6,0,0,1,2] )。 编写一个函数来判断给定的目标值是否存在于数组中。若存在返回 true，否则返回 false。(包含重复元素)
class Solution {
public boolean search(int[] nums, int target) {
int left = 0, len = nums.length, right = len - 1;
if (len == 0) {
return false;
}
if (len == 1) {
return nums[0] == target ? true :false;
}
while (left <= right) {
int mid = left + ((right - left) >> 1);
if (nums[mid] == target) {
return true;
}
if (nums[left] == nums[mid]) {
left++;
continue;
}
// 左半段
if (nums[left] <= nums[mid]) {
// 左半段左部
if (nums[left] <= target && target < nums[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
} else { // 右半段
// 右半段右部
if (target > nums[mid] && target <= nums[right]) {
left = mid + 1;
} else {
right = mid - 1;
}
}
}
return false;
}
}二分搜索核心四点要素（必背&理解）
- 1、初始化：start=0、end=len-1
- 2、循环退出条件：start + 1 < end
- 3、比较中点和目标值：A[mid] ==、 <、> target
- 4、判断最后两个元素是否符合：A[start]、A[end] ? target