二分法的详解与扩展
1）在一个有序数组中，找某个数是否存在 : 二分
2）在一个有序数组中，找>=某个数最左侧的位置
3）局部最小值问题
1）在一个有序数组中，找某个数是否存在 : 二分法原理
二分查找算法的时间复杂度为 O(log n)，适用于大规模数据的快速查找。
二分查找的原理
二分查找的基本思想是通过不断地将查找范围缩小一半来定位目标值。具体步骤如下：
- 初始化查找范围，设定左边界
left和右边界right。 - 计算中间位置
mid。 - 比较目标值
target与arr[mid]的大小：- 如果
target等于arr[mid]，则找到了目标值，返回True。 - 如果
target小于arr[mid]，则目标值在左半部分，更新右边界right = mid - 1。 - 如果
target大于arr[mid]，则目标值在右半部分，更新左边界left = mid + 1。
- 如果
- 重复步骤 2 和 3，直到查找范围为空（即
left > right）。如果查找范围为空且未找到目标值，则返回False。
二分查找的实现
def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = left + (right - left) // 2
if arr[mid] == target:
return True
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return False
def exit(sortedArr, num):
if sortedArr == None or len(sortedArr) == 0:
return False
L = 0
R = len(sortedArr) - 1
while L < R:
mid = L + ((R - L) >> 1)
if sortedArr[mid] == num:
return True
elif sortedArr[mid] > num:
R = mid - 1
else:
L = mid + 1
return sortedArr[L] == num
# 在arr上，找满足>=value的最左位置
def nearestIndex(arr, value):
L, R = 0, len(arr)-1
ind = -1
while L < R:
mid = L + ((R - L) >> 1)
if arr[mid] >= value:
ind = mid
R = mid - 1
else:
L = mid + 1
return ind
解释
- 初始化查找范围：
left初始为 0，right初始为数组长度减 1。 - 计算中间位置：
mid = left + (right - left) // 2。这种计算方法可以避免大数相加时的整数溢出问题。 - 比较目标值与中间值：
- 如果
arr[mid] == target，返回True。 - 如果
arr[mid] < target，更新左边界left = mid + 1。 - 如果
arr[mid] > target，更新右边界right = mid - 1。
- 如果
- 重复步骤 2 和 3，直到
left > right。如果查找范围为空且未找到目标值，返回False。
时间和空间复杂度
- 时间复杂度：O(log n)，因为每次查找范围都减半。
- 空间复杂度：O(1)，因为只使用了常数级别的额外空间。
2）在一个有序数组中，找>=某个数最左侧的位置
在一个有序数组中查找大于等于某个数的最左侧位置，可以使用二分查找（Binary Search）算法的变种。
这个问题的具体要求是找到数组中第一个大于等于目标值的位置。使用二分查找可以在 O(log n) 的时间复杂度内高效完成这个任务。
二分查找变种的原理
这个问题的基本思路是使用二分查找来定位第一个大于等于目标值 target 的位置。具体步骤如下：
- 初始化查找范围，设定左边界
left和右边界right。 - 计算中间位置
mid。 - 比较目标值
target与arr[mid]的大小：- 如果
arr[mid]大于等于target，则目标值在左半部分，更新右边界right = mid - 1，并记录当前的mid作为候选位置。 - 如果
arr[mid]小于target，则目标值在右半部分，更新左边界left = mid + 1。
- 如果
- 重复步骤 2 和 3，直到查找范围为空（即
left > right）。最终返回记录的候选位置。
二分查找变种的实现
以下是查找大于等于某个数的最左侧位置的 Python 实现：
def find_leftmost_ge(arr, target):
left, right = 0, len(arr) - 1
result = -1 # 初始化结果为 -1，表示未找到
while left <= right:
mid = left + (right - left) // 2
if arr[mid] >= target:
result = mid # 记录当前的候选位置
right = mid - 1 # 缩小查找范围到左半部分
else:
left = mid + 1 # 缩小查找范围到右半部分
return result
3） 局部最小值问题
示例
- 对于数组 `[9, 6, 3, 14, 5, 7, 4]`，元素 `6` 和 `3` 都是局部最小值。
- 对于数组 `[1, 2, 3, 4, 5]`，元素 `1` 是局部最小值。
- 对于数组 `[5, 4, 3, 2, 1]`，元素 `1` 是局部最小值。
算法思路
采用二分查找的思路，可以在 O(log n) 的时间复杂度内找到一个局部最小值。具体步骤如下：
- 如果数组长度为 1，则直接返回该元素。
- 如果数组长度大于 1，检查数组的边界元素：
- 如果第一个元素小于或等于第二个元素，则第一个元素为局部最小值。
- 如果最后一个元素小于或等于倒数第二个元素，则最后一个元素为局部最小值。
- 如果上述条件都不满足，进行二分查找：
- 计算中间位置
mid。 - 如果
arr[mid]小于或等于arr[mid - 1]和arr[mid + 1]，则arr[mid]为局部最小值。 - 如果
arr[mid - 1]小于arr[mid]，则局部最小值在左半部分，更新右边界right = mid - 1。 - 如果
arr[mid + 1]小于arr[mid], 则局部最小值在右半部分，更新左边界left = mid + 1。
- 计算中间位置
通过使用二分查找的变种算法，可以高效地在无序数组中找到一个局部最小值。这个算法在大规模数据的查找中表现出色，时间复杂度为 O(log n)。
算法实现
以下是使用二分查找法找到局部最小值的 Python 实现：
def find_local_minimum(arr):
n = len(arr)
if n == 0:
return -1
if n == 1:
return -1
if arr[0] <= arr[1]:
return 0
if arr[n - 1] <= arr[n - 2]:
return n - 1
left, right = 0, n - 1
while left <= right:
mid = left + (right - left) // 2
if arr[mid] <= arr[mid - 1] and arr[mid] <= arr[mid + 1]:
return mid
elif mid > 0 and arr[mid - 1] < arr[mid]:
right = mid - 1
else:
left = mid + 1
return None
def getLessIndex(arr):
if arr == None or len(arr)==0:
return -1
if len(arr) == 1 or arr[0] < arr[1]:
return 0
lens = len(arr)
if arr[lens-1] < arr[lens-2]:
return lens - 1
left = 1
right = lens - 2
mid = 0
while left < right:
mid = left + ((right - left) >> 1)
if arr[mid] > arr[mid-1]:
right = mid - 1
elif arr[mid] > arr[mid+1]:
left = mid + 1
else:
return mid
return left
![修复 ITunes 在 Windows 或 Mac 上不断崩溃的问题 [100% 有效]](https://img-blog.csdnimg.cn/direct/913f3f6655b34a568ef7829ea95f58c9.jpeg)
