c语言

C语言怎么实现二分法

小亿
236
2023-11-14 01:37:23
栏目: 编程语言

二分法(Binary Search)是一种在有序数组中查找特定元素的搜索算法。下面是用C语言实现二分法的示例代码:

#include <stdio.h>

// 二分法查找函数
int binarySearch(int arr[], int left, int right, int target) {
    while (left <= right) {
        int mid = left + (right - left) / 2;

        // 如果目标值等于中间值,直接返回
        if (arr[mid] == target) {
            return mid;
        }

        // 如果目标值小于中间值,在左半部分继续查找
        if (arr[mid] > target) {
            right = mid - 1;
        }

        // 如果目标值大于中间值,在右半部分继续查找
        if (arr[mid] < target) {
            left = mid + 1;
        }
    }

    // 目标值不存在于数组中,返回-1
    return -1;
}

int main() {
    int arr[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
    int target = 23;
    int arrSize = sizeof(arr) / sizeof(arr[0]);

    // 在有序数组中查找目标值
    int result = binarySearch(arr, 0, arrSize - 1, target);

    if (result == -1) {
        printf("目标值 %d 不存在于数组中\n", target);
    } else {
        printf("目标值 %d 存在于数组中,索引为 %d\n", target, result);
    }

    return 0;
}

以上代码中,我们定义了一个binarySearch()函数来实现二分法查找。首先传入有序数组、左边界、右边界和目标值作为参数。在函数内部,通过不断调整左边界和右边界的值,每次取中间值与目标值进行比较,直到找到目标值或者左边界大于右边界为止。

main()函数中,我们定义了一个有序数组arr,并将目标值target设置为23。然后调用binarySearch()函数来查找目标值在数组中的索引。最后,根据返回的结果输出相应的信息。

以上代码输出结果为:目标值 23 存在于数组中,索引为 5。表示目标值23在数组中的索引为5。

0
看了该问题的人还看了