C语言实现下界二分查找

好的，下界二分查找的思路是先用二分查找找到目标值的位置，然后往左继续二分查找，直到找到第一个小于等于目标值的位置。具体的代码实现如下：

int lower_bound(int* arr, int n, int target) {
    int left = 0, right = n - 1, res = -1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] >= target) {
            res = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return res;
}

其中，arr 表示要查找的数组，n 表示数组的长度，target 表示要查找的目标值。函数返回的是小于等于目标值的最大下标，如果不存在小于等于目标值的元素，返回 -1。

注意，这个代码实现是针对升序数组的，如果是降序数组，需要将第 6 行和第 8 行的符号反转即可。

相关问题

C语言实现无序的顺序查找（0的位置放哨兵）；有序的折半查找；

**无序顺序查找（Unordered Linear Search with Sentinel）**：
在C语言中，无序顺序查找也叫线性查找，它的基本思想是从数组的第一个元素开始逐个比较，直到找到目标元素或遍历完整个数组。由于题目提到的是0作为哨兵，意味着数组的第一个元素实际上是索引为1的元素。以下是简单实现：

int unordered_search(int arr[], int target, int n) {
    int i;
    for (i = 1; i <= n; i++) { // 跳过哨兵0
        if (arr[i] == target) {
            return i; // 找到目标，返回其位置
        }
    }
    return -1; // 没找到，返回-1表示不存在
}

**有序折半查找（Binary Search）**：
对于有序数组，折半查找（也称为二分查找）效率更高。它是通过不断将查找区间缩小一半的方式进行的。以下是C语言实现：

int ordered_binary_search(int arr[], int target, int low, int high) {
    while (low <= high) {
        int mid = (low + high) / 2;
        
        if (arr[mid] == target) {
            return mid; // 找到目标，返回其位置
        } else if (arr[mid] < target) {
            low = mid + 1; // 目标在右半部分，调整下限
        } else {
            high = mid - 1; // 目标在左半部分，调整上限
        }
    }
    
    return -1; // 没找到，返回-1表示不存在
}

在这段代码里，`low` 和 `high` 分别表示当前查找区间的下界和上界。

试写出二分查找的算法，用low和high来表示当前查找区间的上界和下界，mid为中间位置

好的，以下是二分查找算法的示例代码（使用C语言）：

int binary_search(int arr[], int n, int target) {
    int low = 0, high = n-1;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return -1;
}

其中，arr为待查找的有序数组，n为数组的长度，target为需要查找的目标值。在二分查找中，我们通过将查找区间不断缩小一半，来逐步逼近目标值。

在代码中，我们使用low和high来表示当前查找区间的上界和下界，初始时low为0，high为n-1。在每一轮查找中，我们通过计算mid来找到当前查找区间的中间位置。如果arr[mid]等于target，则直接返回mid；如果arr[mid]小于target，则说明目标值在mid的右侧，因此需要将查找区间缩小到mid+1到high；如果arr[mid]大于target，则说明目标值在mid的左侧，因此需要将查找区间缩小到low到mid-1。最终，如果没有找到目标值，则返回-1。

希望这个示例代码能够帮到你，如果你还有其他问题，请继续提出。