C 中二分查找的第一次和最后一次出现

计算机

二分查找的第一次和最后一次出现

在计算机科学中，二分查找是一种高效的搜索算法，它在有序数组中查找特定元素的位置。对于某些应用，我们可能需要找到一个元素在数组中第一次出现和最后一次出现的位置。这两个位置的确定对于问题的解决或统计都具有重要意义。

算法原理

二分查找是一种分而治之的算法，它通过将问题分解为更小的子问题来解决。在有序数组中，算法首先确定中间元素，然后将搜索范围缩小为左侧或右侧子数组。这个过程一直重复，直到找到目标元素或确定元素不存在。

对于查找第一次出现和最后一次出现的位置，我们需要对二分查找进行修改。具体来说，我们在找到目标元素时不立即返回，而是继续在左半部分或右半部分继续查找，以确定第一次和最后一次出现的位置。

查找第一次出现的位置

当找到目标元素时，我们向左侧继续查找，直到左侧不再存在目标元素。此时，当前位置即为目标元素第一次出现的位置。

查找最后一次出现的位置

当找到目标元素时，我们向右侧继续查找，直到右侧不再存在目标元素。此时，当前位置即为目标元素最后一次出现的位置。

示例代码

下面是一个使用C语言实现的简单示例代码，演示了如何查找有序数组中元素的第一次和最后一次出现的位置：

c
#include <stdio.h>
int binarySearchFirst(int arr[], int n, int target) {
    int low = 0, high = n - 1, result = -1;
    while (low <= high) {</p>        int mid = low + (high - low) / 2;
        if (arr[mid] == target) {
            result = mid;
            high = mid - 1;  // 继续在左侧查找
        } else if (arr[mid] < target) {</p>            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return result;
}
int binarySearchLast(int arr[], int n, int target) {
    int low = 0, high = n - 1, result = -1;
    while (low <= high) {</p>        int mid = low + (high - low) / 2;
        if (arr[mid] == target) {
            result = mid;
            low = mid + 1;  // 继续在右侧查找
        } else if (arr[mid] < target) {</p>            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return result;
}
int mAIn() {
    int arr[] = {1, 2, 2, 4, 5, 5, 5, 8, 9};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 5;
    int firstOccurrence = binarySearchFirst(arr, n, target);
    int lastOccurrence = binarySearchLast(arr, n, target);
    printf("第一次出现的位置：%d%
", firstOccurrence);
    printf("最后一次出现的位置：%d%
", lastOccurrence);
    return 0;
}

这个示例代码中，binarySearchFirst和binarySearchLast分别用于查找第一次和最后一次出现的位置。在主函数中，我们定义了一个有序数组，然后调用这两个函数查找元素5的第一次和最后一次出现的位置，并输出结果。

通过这种方式，我们可以在有序数组中高效地确定元素第一次和最后一次出现的位置，为进一步处理问题提供了基础。