首先我们做一个小小的变换，将原数组 nums 转换为 A，其中 A[i] = nums[i] - i。这样 新的数组 A 就是一个不严格递增的数组。这样原问题转换为 在一个不严格递增的数组 A 中找第一个等于 0 的索引。接下来，我们就可以使用最左满足模板，找到最左满足 nums[i] == i 的索引。
代码：
class Solution:
def solve(self, nums):
l, r = 0, len(nums) - 1
while l <= r:
mid = (l + r) // 2
if nums[mid] >= mid:
r = mid - 1
else:
l = mid + 1
return l if l < len(nums) and nums[l] == l else -1
寻找最右边的满足条件的值
和查找一个数类似， 我们仍然套用查找一个数的思维框架和代码模板。
有没有感受到框架和模板的力量？
思维框架
首先定义搜索区间为 [left, right]，注意是左右都闭合，之后会用到这个点。
你可以定义别的搜索区间形式，不过后面的代码也相应要调整，感兴趣的可以试试别的搜 索区间。
由于我们定义的搜索区间为 [left, right]，因此当 left <= right 的时候，搜索区间 都不为空。 也就是说我们的终止搜索条件为 left <= right。
def bisect_left(A, x):
# 内置 api
bisect.bisect_left(A, x)
# 手写
l, r = 0, len(A) - 1
while l <= r:
mid = (l + r) // 2
if A[mid] >= x: r = mid - 1
else: l = mid + 1
return l
Java
import java.util.*;
public class BinarySearch {
public int getPos(int[] A, int val) {
int low=0,high=A.lenght-1;
while (low <= high){
int mid = (low + high)/2;
if (A[mid] >= val) {
high = mid-1;
} else {
low = mid+1;
}
}
return low;
}
}
C++
public:
int binarySearch(int* arr, int arrLen,int a) {
int left = 0;
int right = arrLen - 1;
while(left<=right)
{
int mid = (left+right)/2;
if(arr[mid]>=a)
right = mid - 1;
else
left = mid + 1;
}
return left;
}
JavaScript
function binarySearch(nums, target) {
let left = 0;
let right = nums.length - 1;
while (left <= right) {
const mid = Math.floor(left + (right - left) / 2);
if (nums[mid] >= target) {
// 搜索区间变为 [left, mid-1]
right = mid - 1;
}
else {
// 搜索区间变为 [mid+1, right]
left = mid + 1;
}
}
return left;
}
寻找最右插入位置
思维框架
如果你将寻找最右插入位置看成是寻找最右满足大于 x 的值，那就可以和前面的 知识产生联系，使得代码更加统一。唯一的区别点在于前面是最左满足等于 x，这里 是最左满足大于 x。
具体算法：
首先定义搜索区间为 [left, right]，注意是左右都闭合，之后会用到这个点。
你可以定义别的搜索区间形式，不过后面的代码也相应要调整，感兴趣的可以试试别的搜 索区间。
由于我们定义的搜索区间为 [left, right]，因此当 left <= right 的时候，搜索区间 都不为空。 也就是说我们的终止搜索条件为 left <= right。
def bisect_right(A, x):
# 内置 api
bisect.bisect_right(A, x)
# 手写
l, r = 0, len(A) - 1
while l <= r:
mid = (l + r) // 2
if A[mid] <= x: l = mid + 1
else: r = mid - 1
return l # 或者返回 r + 1
Java
import java.util.*;
public class BinarySearch {
public int getPos(int[] A, int val) {
int low=0,high=A.lenght-1;
while (low <= high){
int mid = (low + high)/2;
if (A[mid] <= val) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return low;
}
}
C++
public:
int binarySearch(int* arr, int arrLen,int a) {
int left = 0;
int right = arrLen - 1;
while(left<=right)
{
int mid = (left+right)/2;
if(arr[mid]<=a)
// 搜索区间变为 [mid+1, right]
left = mid + 1;
else
// 搜索区间变为 [left, mid-1]
right = mid - 1;
}
return left;
}
JavaScript
function binarySearch(nums, target) {
let left = 0;
let right = nums.length - 1;
while (left <= right) {
const mid = Math.floor(left + (right - left) / 2);
if (nums[mid] <= target) {
// 搜索区间变为 [mid+1, right]
left = mid + 1;
}
else {
// 搜索区间变为 [left, mid-1]
right = mid - 1;
}
}
return left;
}
class Solution:
def search(self, nums, target):
l, r = 0, len(nums)-1
while l <= r:
mid = l + (r-l)//2
if nums[mid] == target:
return True
while l < mid and nums[l] == nums[mid]: # tricky part
l += 1
# the first half is ordered
if nums[l] <= nums[mid]:
# target is in the first half
if nums[l] <= target < nums[mid]:
r = mid - 1
else:
l = mid + 1
# the second half is ordered
else:
# target is in the second half
if nums[mid] < target <= nums[r]:
l = mid + 1
else:
r = mid - 1
return False
class Solution:
def search(self, nums: List[int], target: int) -> int:
l, r = 0, len(nums) - 1
while l <= r:
mid = l + (r - l) // 2
# # the first half is ordered
if nums[l] < nums[mid]:
# target is in the first half
if nums[l] <= target <= nums[mid]:
r = mid - 1
else:
l = mid + 1
# # the second half is ordered
elif nums[l] > nums[mid]:
# target is in the second half
if nums[l] <= target or target <= nums[mid]:
r = mid - 1
else:
l = mid + 1
elif nums[l] == nums[mid]:
if nums[l] != target:
l += 1
else:
# l 是一个备胎
r = l - 1
return l if l < len(nums) and nums[l] == target else -1
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
m = len(matrix)
if m == 0:
return False
n = len(matrix[0])
x = m - 1
y = 0
while x >= 0 and y < n:
if matrix[x][y] > target:
x -= 1
elif matrix[x][y] < target:
y += 1
else:
return True
return False
class Solution:
def findMin(self, nums: List[int]) -> int:
l, r = 0, len(nums) - 1
while l < r:
# important
if nums[l] < nums[r]:
return nums[l]
mid = (l + r) // 2
# left part
if nums[mid] > nums[r]:
l = mid + 1
else:
# right part
r = mid
# l or r is not important
return nums[l]
复杂度分析
时间复杂度：$O(log N)$
空间复杂度：$O(1)$
另一种二分法
思路
我们当然也也可以和 nums[l] 比较，而不是上面的 nums[r]，我们发现：
旋转点左侧元素都大于数组第一个元素
旋转点右侧元素都小于数组第一个元素
这样就建立了 nums[mid] 和 nums[0] 的联系。
具体算法：
找到数组的中间元素 mid。
如果中间元素 > 数组第一个元素，我们需要在 mid 右边搜索。
如果中间元素 <= 数组第一个元素，我们需要在 mid 左边搜索。
上面的例子中，中间元素 6 比第一个元素 4 大，因此在中间点右侧继续搜索。
当我们找到旋转点时停止搜索，当以下条件满足任意一个即可：
nums[mid] > nums[mid + 1]，因此 mid+1 是最小值。
nums[mid - 1] > nums[mid]，因此 mid 是最小值。
代码（Python）
class Solution:
def findMin(self, nums):
# If the list has just one element then return that element.
if len(nums) == 1:
return nums[0]
# left pointer
left = 0
# right pointer
right = len(nums) - 1
# if the last element is greater than the first element then there is no rotation.
# e.g. 1 < 2 < 3 < 4 < 5 < 7. Already sorted array.
# Hence the smallest element is first element. A[0]
if nums[right] > nums[0]:
return nums[0]
# Binary search way
while right >= left:
# Find the mid element
mid = left + (right - left) / 2
# if the mid element is greater than its next element then mid+1 element is the smallest
# This point would be the point of change. From higher to lower value.
if nums[mid] > nums[mid + 1]:
return nums[mid + 1]
# if the mid element is lesser than its previous element then mid element is the smallest
if nums[mid - 1] > nums[mid]:
return nums[mid]
# if the mid elements value is greater than the 0th element this means
# the least value is still somewhere to the right as we are still dealing with elements greater than nums[0]
if nums[mid] > nums[0]:
left = mid + 1
# if nums[0] is greater than the mid value then this means the smallest value is somewhere to the left
else:
right = mid - 1
