二分查找的应用与实现

二分查找是一种在数组查找元素位置的高效算法，时间复杂度为O(log n)，广泛应用于排序数组中的元素查找、 Bounds 检查以及查找特定元素的位置等场景。其核心逻辑是通过不断缩小查找范围，直到找到目标元素或确定其不存在。

1. 基础二分查找：查找是否存在元素e

#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，表示目标元素不存在。

2. 查找数组中最大值的位置

当数组中存在目标值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。

3. 查找数组中最小值的位置

类似地，我们可以修改条件来查找目标值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。

4. 寻找不存在目标值时的Bounds

在不知道目标值是否存在的情况下，我们可以利用二分查找来找到：

方括号的最大值（即找到第一个大于等于e的值的位置）

方括号的最小值（即找到第一个小于等于e的值的位置）

这可以通过调整查找条件来实现。

查找方括号的最大值：

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的值的位置。

5. 二分查找浮点数值解

对于单调函数的值问题，二分法是一种直接的解决方案。以下是一个简单的浮点数值解的示例：

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/

你可能感兴趣的文章