基于C的二分法查找代码

以下是基于C的二分法查找代码：

#include <stdio.h>

int binarySearch(int arr[], int l, int r, int x) {
    while (l <= r) {
        int mid = l + (r - l) / 2;
        if (arr[mid] == x)
            return mid;
        if (arr[mid] < x)
            l = mid + 1;
        else
            r = mid - 1;
    }
    return -1;
}

int main() {
    int arr[] = {2, 3, 4, 10, 40};
    int n = sizeof(arr) / sizeof(arr[0]);
    int x = 10;
    int result = binarySearch(arr, 0, n - 1, x);
    (result == -1) ? printf("Element is not present in array")
                   : printf("Element is present at index %d", result);
    return 0;
}

这是一个基本的二分法查找代码，它可以在一个有序的数组中查找一个特定的元素。

相关问题

c语言二分法查找代码

以下是C语言实现二分法查找的代码：

int search(int a[], int length, int key) {
    int result = -1;
    int left, right;
    left = 0;
    right = length - 1; // left数组最左值，right数组最右值
    while (right >= left) {
        int middle = (right + left) / 2;
        if (key == a[middle]) {
            result = middle;
            break;
        } else if (key < a[middle]) {
            right = middle - 1;
        } else {
            left = middle + 1;
        }
    }
    return result;
}

该函数接受一个有序数组a、数组长度length和要查找的关键字key作为参数，返回关键字在数组中的下标，如果没有找到则返回-1。

c语言二分法查找特点

C语言二分法查找的特点如下：

int binarySearch(int arr[], int l, int r, int x) {
    while (l <= r) {
        int m = l + (r - l) / 2;
        if (arr[m] == x)
            return m;
        if (arr[m] < x)
            l = m + 1;
 else
            r = m - 1;
    }
    return -1;
}

1. 二分法查找只适用于已排序的数组。
2. 二分法查找的时间复杂度为O(log n)，比线性查找的O(n)更快。
3. 二分法查找的空间复杂度为O(1)，只需要常量级的额外空间。
4. 二分法查找的实现通常使用迭代而不是递归，因为迭代的空间复杂度更低。
5. 二分法查找的实现需要注意边界条件，例如当数组为空或只有一个元素时应该特殊处理。