【leetcode】 数组二分查找
1.二分查找
二分查找（Binary Search），也称为折半查找，是一种在有序数组中查找特定元素的高效算法。它的基本思想是不断将待查找区间缩小一半，直到找到目标元素或确定目标元素不在数组中为止。这种查找方法比线性查找效率高，因为它可以快速排除掉大部分不可能包含目标元素的区间，从而减少了比较次数。
二分查找的工作原理如下：
-
首先，确定查找范围的左边界
left和右边界right，通常初始时left设为数组的起始索引，right设为数组的结束索引。 -
计算中间元素的索引
mid，可以使用(left + right) // 2计算。 -
比较中间元素与目标元素的大小：
- 如果中间元素等于目标元素，查找成功，返回
mid。 - 如果中间元素大于目标元素，说明目标元素可能在左半边，将
right更新为mid - 1，然后重复步骤2。 - 如果中间元素小于目标元素，说明目标元素可能在右半边，将
left更新为mid + 1，然后重复步骤2。
- 如果中间元素等于目标元素，查找成功，返回
-
重复步骤2和步骤3，直到
left大于right，此时说明查找范围为空，目标元素不在数组中，可以返回-1或其他指定的标志来表示查找失败。
二分查找的时间复杂度是 O(log n)，其中 n 是数组的长度。由于每次查找都将查找范围缩小一半，因此它在大型有序数组中表现出色，是一种高效的查找算法。但要使用二分查找，前提是数组必须是有序的，否则无法保证正确的查找结果。
2.举个例子
当使用二分查找时，通常需要一个有序数组。以下是一个简单的例子，演示如何使用二分查找在有序数组中查找特定的目标元素。
假设有一个有序整数数组 nums 如下：
nums = [2, 4, 6, 8, 10, 12, 14, 16, 18, 20]
现在，我们要查找数字 12 是否在这个数组中，并返回其索引位置。我们可以使用二分查找来实现：
- 初始化左边界
left为 0，右边界right为数组的长度减一，即left = 0，right = 9。 - 计算中间索引
mid，mid = (0 + 9) // 2 = 4。 - 比较
nums[4]（即数组的中间元素10）与目标元素12：- 因为
10 < 12，所以目标元素可能在右半部分，更新left为mid + 1，即left = 5。
- 因为
- 重复步骤2和步骤3：
- 计算中间索引
mid，mid = (5 + 9) // 2 = 7。 - 比较
nums[7]（即数组的中间元素16）与目标元素12：- 因为
16 > 12，所以目标元素可能在左半部分，更新right为mid - 1，即right = 6。
- 因为
- 计算中间索引
- 重复步骤2和步骤3：
- 计算中间索引
mid，mid = (5 + 6) // 2 = 5。 - 比较
nums[5]（即数组的中间元素12）与目标元素12：- 因为
12 == 12，查找成功，返回mid = 5。
- 因为
- 计算中间索引
最终，我们通过二分查找找到了目标元素 12，并返回它在数组中的索引位置为 5。这个例子演示了如何使用二分查找在有序数组中快速查找目标元素。这个算法在大型有序数组中的效率非常高，因为它可以快速排除掉一半的元素。
以下是使用Python实现的二分查找算法的示例代码：
def binary_search(nums, target):
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
return mid # 找到目标元素，返回索引
elif nums[mid] < target:
left = mid + 1 # 目标元素在右半部分
else:
right = mid - 1 # 目标元素在左半部分
return -1 # 目标元素不在数组中
# 示例用法
nums = [2, 4, 6, 8, 10, 12, 14, 16, 18, 20]
target = 12
result = binary_search(nums, target)
if result != -1:
print(f"目标元素 {target} 在数组中的索引位置是 {result}")
else:
print(f"目标元素 {target} 不在数组中")
这段代码实现了一个名为 binary_search 的函数，该函数接受一个有序数组 nums 和要查找的目标元素 target 作为参数。它使用一个循环来在数组中执行二分查找，不断更新 left 和 right 边界，直到找到目标元素或确定它不在数组中。如果找到目标元素，函数返回目标元素的索引；否则，返回 -1 表示目标元素不在数组中。
在示例用法中，我们使用有序数组 nums 进行二分查找，查找目标元素 12，并输出结果。这个例子演示了如何使用二分查找函数来查找目标元素。
3.二分查找的进阶
在进行二分查找时，有一些进阶技巧和注意事项可以帮助你更好地处理边界情况、提高效率，以及适应不同的问题。以下是一些进阶方面的考虑：
-
边界判断：
- 在进入二分查找循环之前，通常需要确保输入数据是有效的，例如，数组不为空。
- 在更新边界
left和right时，需要注意边界情况，确保不会越界。
-
中值选取：
- 通常，中值
mid的计算可以使用(left + right) // 2，但如果left和right很大，相加可能会导致整数溢出。为了避免这种情况，可以使用left + (right - left) // 2来计算中值。 - 如果使用编程语言支持的浮点数类型，也可以使用
left + (right - left) / 2.0来计算中值。
- 通常，中值
-
查找变种：
- 二分查找通常用于在有序数组中查找目标元素，但也可以通过变种来处理其他问题，如查找第一个出现的目标元素、最后一个出现的目标元素或第一个大于/小于目标元素的元素。
- 这些变种可以通过稍微修改二分查找的条件来实现。
-
左闭右开区间：
- 有时，为了避免边界问题，可以使用左闭右开区间来进行二分查找。即，定义
right为数组长度，但在比较中不包括nums[right]。 - 这可以简化边界处理，但需要在结果中进行相应的调整。
- 有时，为了避免边界问题，可以使用左闭右开区间来进行二分查找。即，定义
-
递归实现：
- 除了迭代实现外，还可以使用递归来实现二分查找。递归实现通常更简洁，但可能会占用更多的内存空间。
-
特殊条件：
- 在某些情况下，可以根据特殊条件提前终止二分查找，而不必等到完全找到目标元素。这可以提高效率，尤其是在大规模数据上。
-
性能优化：
- 对于非常大的数据集，可能需要考虑性能优化。例如，可以使用二分查找的变种，如插值查找或斐波那契查找，以加速查找过程。
这些是在进行二分查找时的一些进阶技巧和注意事项。具体实现时，要根据问题的要求和数据特点来选择合适的策略和边界条件。
4.leetcode原题
当涉及到进阶的二分查找问题时，LeetCode上有许多具有一定难度的原题。以下是一些比较复杂的LeetCode二分查找问题的示例：
-
搜索旋转排序数组 II (Search in Rotated Sorted Array II)
- 问题描述：给定一个包含重复元素的升序排序数组，判断某个目标元素是否存在其中。
- 难度：中等
- 链接：https://leetcode.com/problems/search-in-rotated-sorted-array-ii/
-
寻找旋转排序数组中的最小值 II (Find Minimum in Rotated Sorted Array II)
- 问题描述：给定一个包含重复元素的升序排序数组，查找数组中的最小元素。
- 难度：困难
- 链接：https://leetcode.com/problems/find-minimum-in-rotated-sorted-array-ii/
-
寻找峰值 II (Find Peak Element II)
- 问题描述：给定一个二维矩阵，查找其中的峰值元素。一个峰值元素是指其值大于或等于相邻元素的值。
- 难度：困难
- 链接：https://leetcode.com/problems/find-peak-element-ii/
-
搜索二维矩阵 II (Search a 2D Matrix II)
- 问题描述：给定一个二维矩阵，其中的每行和每列都按升序排列，编写一个函数来查找目标值是否存在其中。
- 难度：中等
- 链接：https://leetcode.com/problems/search-a-2d-matrix-ii/
这些问题都具有一定的难度，需要对二分查找算法有深入的理解和应用。解决它们需要灵活运用二分查找的思想，并考虑特殊情况和边界条件。如果你想挑战更复杂的二分查找问题，可以尝试解决上述LeetCode题目。
