二分查找法的算法过程包括
在计算机科学中，二分查找法也被称为折半查找法。它是一种在有序数组中查找特定元素的算法。该算法使用分而治之的策略，通过不断将目标值与数组中间的元素比较，缩小查找范围，直到找到目标值或确定其不存在。
算法过程：
假设要在一个已排序的数组中查找特定元素target：
1.定义左指针left和右指针right，初始值分别为数组的起始位置和结尾位置。
2.计算中心索引mid，mid = (left + right) / 2。
3.比较中心元素与target的大小。如果mid元素等于target，则返回mid，否则，如果mid元素大于target，则在左半边继续查找，更新right的值，right = mid - 1，否则，在右半边继续查找，更新left的值，left = mid + 1。
4.重复执行步骤2-3，直到找到target或者left>right结束查找。
这个算法的时间复杂度为O(logn)，是一种高效的查找方法，特别适用于大型有序数组。
二分查找法的特点：
1.二分查找法的执行前提是数组中的元素必须已按升序或降序进行排序，否则无法执行查找。
2.二分查找法的应用范围广泛，同时可以解决许多问题，例如查找中位数、寻找第k个最大元素等。
3.二分查找法的时间复杂度是O(logn)，比其他查找方法效率更高。因此，它也是编写高效程序的重要技巧之一。
除此之外，二分查找法还有一些高级应用，值得深入研究。
1. 查找左右边界
当我们需要查找有序数组中大于或等于某个元素的第一个位置时，或小于或等于某个元素的最后一个位置时，可以通过二分查找法进行。具体来说，我们可以在二分查找过程中记录与target相等的位置，然后在左半边查找大于等于target的第一个元素，以及在右半边查找小于等于target的最后一个元素。如下所示：
int left_bound(vector
int left = 0, right = nums.size() - 1;
int ans = -1;
while (left <= right) {
int mid = (left + right) / 2;
if (nums[mid] >= target) {
ans = mid;
right = mid - 1;
} else {
left = mid + 1;
}
}
return ans;
}
int right_bound(vector
int left = 0, right = nums.size() - 1;
int ans = -1;
while (left <= right) {
int mid = (left + right) / 2;
if (nums[mid] <= target) {
ans = mid;
left = mid + 1;
} else {
right = mid - 1;
}
}
return ans;
}
2. 查找旋转排序数组中的最小值
旋转排序数组是指在原数组的某个位置上进行了旋转的数组。例如[4,5,6,7,0,1,2]是一个旋转排序数组，它在数字7处旋转。我们可以通过二分查找法解决旋转排序数组中的最小值问题。具体来说，我们可以不断将区间缩小，直到区间只剩一个元素，这个元素即为最小值。如下所示：
int findMin(vector
int left = 0, right = nums.size() - 1;
while (left < right) {
int mid = (left + right) / 2;
if (nums[mid] < nums[right]) {
right = mid;
} else if (nums[mid] > nums[right]) {
left = mid + 1;
} else {
right--;
}
}
return nums[left];
}
3. 查找旋转排序数组中的特定值
在旋转排序数组中查找特定值可以通过二分查找来实现。具体来说，我们可以在二分查找中判断mid元素是否等于target，如果是，则直接返回mid索引；否则判断mid所在的区间是否单调递增，如果是，则在该区间中查找target，否则在非单调区间中查找。如下所示：
int search(vector
int left = 0, right = nums.size() - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (nums[mid] == target) {
return mid;
}
if (nums[left] <= nums[mid]) { // 左半区间单调递增
if (nums[left] <= target && target < nums[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
} else { // 右半区间单调递增
if (nums[mid] < target && target <= nums[right]) {
left = mid + 1;
} else {
right = mid - 1;
}
}
}
return -1;
}
综上所述，二分查找法是一种高效的查找方法，特别适用于大型有序数组。它的应用范围广泛，同时还有许多高级用法，如查找左右边界、查找旋转排序数组中的最小值和特定值。因此，我们应该深入了解和掌握这个算法，并在实际编程中灵活应用。
