本文共 3109 字，大约阅读时间需要 10 分钟。
二分查找是一种在数组查找元素位置的高效算法，时间复杂度为O(log n)，广泛应用于排序数组中的元素查找、 Bounds 检查以及查找特定元素的位置等场景。其核心逻辑是通过不断缩小查找范围，直到找到目标元素或确定其不存在。
#include#include int *a = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};int findElement(int l, int r, int e) { while (l <= r) { int mid = l + (r - l > 1 ? (r - l) / 2 : 0); if (a[mid] < e) { l = mid + 1; } else if (a[mid] > e) { r = mid - 1; } else { return mid; } } return -1;}int main() { int target; while (scanf("%d", &target) != EOF) { int pos = findElement(0, 10, target); if (pos == -1) { printf("目标元素不存在\n"); } else { printf("元素在数组中的位置为：%d\n", pos); } } return 0;}
解释：该代码实现了一个基础的二分查找算法，可以用来判断一个元素是否存在于数组中。通过循环缩小查找范围，计算中间点mid，并根据当前元素与目标值的大小关系调整查找方向。当找到目标元素时，返回其位置；如果遍历结束后仍未找到，则返回-1，表示目标元素不存在。
当数组中存在目标值e时，我们需要找到它在数组中的最大位置（最右侧的位置）。这可以通过将右边界的条件设置为a[mid] <= e来实现。
int findMaxPosition(int l, int r, int e) { while (l < r) { int mid = l + ((r - l > 1) ? (r - l + 1) / 2 : 0); if (a[mid] <= e) { l = mid; } else { r = mid; } } if (a[l] == e) { return l; } return -1;} 解释：在这个版本中，二分查找的终止条件发生了变化。通过将右边界的条件改为a[mid] <= e，我们逐渐缩小到最右侧的位置。最终，当循环结束时，l会停在目标值e的最右侧位置。如果目标值存在于数组中，返回该位置；否则返回-1。
类似地，我们可以修改条件来查找目标值e的最左侧位置。这种情况下，左边界的条件会被调整为a[mid] >= e。
int findMinPosition(int l, int r, int e) { while (l < r) { int mid = l + ((r - l > 1) ? (r - l) / 2 : 0); if (a[mid] >= e) { r = mid; } else { l = mid + 1; } } if (a[l] == e) { return l; } return -1;} 解释：在这一版本中，我们将左边界的条件改为a[mid] >= e。这样，查找过程会逐渐逼近到目标值e的最左侧位置。当循环结束时，如果找到目标值，返回其位置；否则返回-1。
在不知道目标值是否存在的情况下，我们可以利用二分查找来找到：
这可以通过调整查找条件来实现。
查找方括号的最大值：
int findFloor(int l, int r, int e) { while (l < r) { int mid = l + ((r - l + 1) / 2); if (a[mid] >= e) { r = mid; } else { l = mid + 1; } } return l;} 查找方括号的最小值：
int findCeil(int l, int r, int e) { while (l < r) { int mid = l + ((r - l) / 2); if (a[mid] <= e) { l = mid + 1; } else { r = mid; } } return r;} 解释：
findFloor中，我们找到第一个大于等于e的值的位置。通过调整右边界的节点条件为a[mid] >= e，并逐渐将右边界向左移动。当循环结束时，l会停在第一个大于等于e的值的位置。findCeil中，我们找到第一个小于等于e的值的位置。通过调整左边界的节点条件为a[mid] <= e，并逐渐将左边界向右移动。当循环结束时，r会停在第一个大于e的值的位置。对于单调函数的值问题，二分法是一种直接的解决方案。以下是一个简单的浮点数值解的示例：
double binarySearch(double min, double max, double esp, double (*f)(double)) { double begin = min; double end = max; while (fabs(end - begin) > esp) { double mid = begin + (end - begin) / 2; if (f(mid) > 0) { begin = mid; } else { end = mid; } } return mid;} 解释：该算法用于解决单调函数的值问题。通过不断将搜索范围缩小到中间值，并根据函数值的符号调整边界，直到找到满足精度要求的解。在较复杂的实际问题中，可能需要根据具体函数的行为和数值精度要求进行调整。
通过以上方法，我们可以有效地利用二分查找解决各种场景中的查找问题，显著提升算法的效率。无论是用于整数数组还是浮点数值的单调函数问题，二分查找都提供了高效且可靠的解决方案。
转载地址：http://wbaoz.baihongyu.com/