参考内容：https://greyireland.gitbook.io/algorithm-pattern/ji-chu-suan-fa-pian/binary_search
给一个有序数组和目标值，找第一次/最后一次/任何一次出现的索引，如果没有出现返回-1
模板四点要素
- 初始化：start=0、end=len-1循环退出条件：start + 1 < end比较中点和目标值：A[mid] ==、 <、> target判断最后两个元素是否符合：A[start]、A[end] ? target
时间复杂度 O(logn)，使用场景一般是有序数组的查找
模板：
不论是模板几，基础的思想都是利用判断左右指针与目标值之间的关系不断缩小左右指针包含的范围，最终得出一个确定的值或者确定的区间。
本文大部分将用3，因为可以返回两个指针，将取舍交给while循环结束后进行。当然，简单情况唯一解时用1方便。
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
示例 1:
输入: nums = [-1,0,3,5,9,12], target = 9 输出: 4 解释: 9 出现在 nums 中并且下标为 4
示例 2:
输入: nums = [-1,0,3,5,9,12], target = 2 输出: -1 解释: 2 不存在 nums 中因此返回 -1
提示：
你可以假设 nums 中的所有元素是不重复的。n 将在 [1, 10000]之间。nums 的每个元素都将在 [-9999, 9999]之间。
class Solution {
public int search(int[] nums, int target) {
int n=nums.length;
int left=0,right=n-1;
while(left<=right){
int mid=left+(right-left)/2;
if(target==nums[mid]){
return mid;
}else if(nums[mid]
常见题目
1、搜索区间
描述
给定一个包含 n 个整数的排序数组，找出给定目标值 target 的起始和结束位置。
如果目标值不在数组中，则返回[-1, -1]
样例 1：
输入：
数组 = []
target = 9
输出：
[-1,-1]
解释：
9不在数组中。
样例 2：
输入：
数组 = [5, 7, 7, 8, 8, 10]
target = 8
输出：
[3,4]
解释：
数组的[3,4]子区间值为8。
挑战
时间复杂度 O(log n)
思路
因为是寻找区间，所以要分左右边界进行两次寻找。开始前要注意对数组的判空。
这里使用的是模板三。
public class Solution {
public int[] searchRange(int[] A, int target) {
// write your code here
int n=A.length;
int left=0,right=n-1;
int[] res=new int[2];
res[0]=-1;
res[1]=-1;
if(n==0){
return res;
}
while(left+1target){
right=mid;
}else{
left=mid;
}
}
res[1]=A[right]==target?right:(A[left]==target?left:-1);
return res;
}
}
2、搜索插入位置
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
示例 1:
输入: nums = [1,3,5,6], target = 5
输出: 2
示例 2:
输入: nums = [1,3,5,6], target = 2
输出: 1
示例 3:
输入: nums = [1,3,5,6], target = 7
输出: 4
示例 4:
输入: nums = [1,3,5,6], target = 0
输出: 0
示例 5:
输入: nums = [1], target = 0
输出: 0
提示:
1 <= nums.length <= 104-104 <= nums[i] <= 104nums 为无重复元素的升序排列数组 -104 <= target <= 104
思路
找到target或者找到target应该插入的位置，也就是返回第一个≥target的元素的索引。
class Solution {
public int searchInsert(int[] nums, int target) {
int n=nums.length;
int left=0;
int right=n-1;
while(left+1target){
right=mid;
}else{
left=mid;
}
}
if(nums[left]>=target){
return left;
}else if(nums[right]=target){
return right;
}
return -1;
}
}
3、搜索二维矩阵
编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：
每行中的整数从左到右按升序排列。
每行的第一个整数大于前一行的最后一个整数。
示例 1：
输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出：true
示例 2：
输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
输出：false
提示：
m == matrix.lengthn == matrix[i].length1 <= m, n <= 100-104 <= matrix[i][j], target <= 104
思路
将题目目标进行分解：二维矩阵中找到目标值---->找到目标值所在的行---->在目标行寻找目标值
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int m=matrix.length;
int n=matrix[0].length;
//找目标行
int up=0;
int down=m-1;
while(up+1=target){
down=mid;
}else{
up=mid;
}
}
//使用模板3，需要筛选up和down
int row=0;
if(matrix[down][0]target){
row=up;
}
//在目标行找target
int left=0;
int right=n-1;
//这里是找一个确定的值,直接使用模板1
while(left<=right){
int mid=left+(right-left)/2;
if(matrix[row][mid]==target){
return true;
}else if(matrix[row][mid]>target){
right=mid-1;
}else{
left=mid+1;
}
}
return false;
}
}
4、寻找旋转排序数组中的最小值
已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：
若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]
若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]
注意，数组 [a[0], a[1], a[2], …, a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], …, a[n-2]] 。
给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。
示例 1：
输入：nums = [3,4,5,1,2]
输出：1
解释：原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。
示例 2：
输入：nums = [4,5,6,7,0,1,2]
输出：0
解释：原数组为 [0,1,2,4,5,6,7] ，旋转 4 次得到输入数组。
示例 3：
输入：nums = [11,13,15,17]
输出：11
解释：原数组为 [11,13,15,17] ，旋转 4 次得到输入数组。
提示：
n == nums.length
1 <= n <= 5000
-5000 <= nums[i] <= 5000
nums 中的所有整数 互不相同
nums 原来是一个升序排序的数组，并进行了 1 至 n 次旋转
思路
找旋转后的数组中的最小值---->定位最小值在当前序列的左半端还是右半段---->判断最小值在该段的条件
图片来源:力扣官方题解
两种情况：
mid值小于right值，则说明右侧序列是单调递增的，最小值位于左半部分(包含mid)mid值大于right值，说明mid之前的部分都是通过旋转来到数组最前列的，那么最小值一定在mid的右侧
class Solution {
public int findMin(int[] nums) {
int n=nums.length;
if(n==0){
return -1;
}
int left=0;
int right=n-1;
while(left+1nums[right]){
left=mid+1;
}else{
right=mid;
}
}
return Math.min(nums[left],nums[right]);
}
}
5、寻找旋转排序数组中的最小值 II
已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,4,4,5,6,7] 在变化后可能得到：
若旋转 4 次，则可以得到 [4,5,6,7,0,1,4]若旋转 7 次，则可以得到 [0,1,4,4,5,6,7]
注意，数组 [a[0], a[1], a[2], …, a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], …, a[n-2]] 。
给你一个可能存在 重复 元素值的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。
示例 1：
输入：nums = [1,3,5]
输出：1
示例 2：
输入：nums = [2,2,2,0,1]
输出：0
提示：
n == nums.length1 <= n <= 5000-5000 <= nums[i] <= 5000nums 原来是一个升序排序的数组，并进行了 1 至 n 次旋转
思路
变式题和上题不同的是，数组的严格递增不在保证，当mid的元素值等于right的元素值时，我们无法判定最小值在mid的左侧还是右侧。那么上述代码中对mid和right对应值的判断多出了一个特殊情况：array[mid]==array[right]，此时为了不丢失可能为最小值的元素，只能对确定不为最小值的right指针左移一步。
class Solution {
public int findMin(int[] nums) {
int n=nums.length;
if(n==0){
return -1;
}
int left=0;
int right=n-1;
while(left+1nums[right]){
left=mid+1;
}else if(nums[mid]==nums[right]){
right--;
}else{
right=mid;
}
}
return Math.min(nums[right],nums[left]);
}
}
6、搜索旋转排序数组
整数数组 nums 按升序排列，数组中的值互不相同 。
在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。
给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。
示例 1：
输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4
示例 2：
输入：nums = [4,5,6,7,0,1,2], target = 3
输出：-1
示例 3：
输入：nums = [1], target = 0
输出：-1
提示：
1 <= nums.length <= 5000
-10^4 <= nums[i] <= 10^4
nums 中的每个值都独一无二
题目数据保证 nums 在预先未知的某个下标上进行了旋转
-10^4 <= target <= 10^4
进阶：你可以设计一个时间复杂度为 O(log n) 的解决方案吗？
思路
解题目的变成了搜索，那么就要在一个确定包含target的区间内二分搜索。
所以：
第一步：找到旋转数组中的最小值，将数组分为两个递增区间，找出target值所在区间；
第二步：在确定的区间进行搜索。
class Solution {
public int search(int[] nums, int target) {
int n=nums.length;
int left=0;
int right=n-1;
//先找到最小值，将nums划分为两个递增数列
while(left+1nums[right]){
left=mid;
}else{
right=mid;
}
}
int minN=nums[left]=nums[minN]){
left=minN;
right=n-1;
}else {
left=0;
right=minN-1;
}
while(left<=right){
int mid=left+(right-left)/2;
if(nums[mid]==target){
return mid;
}else if(nums[mid]
反思
思路稍有麻烦，要进行两次二分搜索，时间复杂度较高。
重新观察数组，例如：[4,5,6,7,1,2]，mid对应6，由于部分旋转，数组在局部仍有序，可以看到分为[4,5,6]和[7,1,2]两个数组后，必然有一个数组是有序的，那么利用排除法，target如果不在这个有序区间内，那么它一定在另一个区间内，否则就不存在。
class Solution {
public int search(int[] nums, int target) {
int n = nums.length;
if (n == 0) {
return -1;
}
if (n == 1) {
return nums[0] == target ? 0 : -1;
}
int l = 0, r = n - 1;
while (l <= r) {
int mid = (l + r) / 2;
if (nums[mid] == target) {
return mid;
}
if (nums[0] <= nums[mid]) {
if (nums[0] <= target && target < nums[mid]) {
r = mid - 1;
} else {
l = mid + 1;
}
} else {
if (nums[mid] < target && target <= nums[n - 1]) {
l = mid + 1;
} else {
r = mid - 1;
}
}
}
return -1;
}
}
7、搜索旋转排序数组 II
已知存在一个按非降序排列的整数数组 nums ，数组中的值不必互不相同。
在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转 ，使数组变为 [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,4,4,5,6,6,7] 在下标 5 处经旋转后可能变为 [4,5,6,6,7,0,1,2,4,4] 。
给你 旋转后 的数组 nums 和一个整数 target ，请你编写一个函数来判断给定的目标值是否存在于数组中。如果 nums 中存在这个目标值 target ，则返回 true ，否则返回 false 。
你必须尽可能减少整个操作步骤。
示例 1：
输入：nums = [2,5,6,0,0,1,2], target = 0
输出：true
示例 2：
输入：nums = [2,5,6,0,0,1,2], target = 3
输出：false
提示：
1 <= nums.length <= 5000
-104 <= nums[i] <= 104
题目数据保证 nums 在预先未知的某个下标上进行了旋转
-104 <= target <= 104
思路
和题目5类似，增加一个==的判断
class Solution {
public boolean search(int[] nums, int target) {
int n=nums.length;
int left=0;
int right=n-1;
while(left<=right){
int mid=left+(right-left)/2;
if(nums[mid]==target){
return true;
}else if(nums[mid]==nums[right]){
right--;
}else if(nums[mid]=target){
left=mid+1;
}else{
right=mid-1;
}
}else{
if(nums[left]<=target&&nums[mid]>target){
right=mid-1;
}else{
left=mid+1;
}
}
}
return false;
}
}
