C语言二分查找代码怎么写

二分查找算法简介

二分查找(Binary Search)是一种在有序数组中查找特定元素的搜索算法，搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较，如果在某一步骤数组为空，则代表找不到，这种搜索算法每一次比较都使搜索范围缩小一半。

C语言实现二分查找的代码

include <stdio.h>
int binary_search(int arr[], int size, int target) {
    int left = 0;
    int right = size 1;
    while (left <= right) {
        int mid = left + (right left) / 2;
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid 1;
        }
    }
    return -1;
}

使用示例

include <stdio.h>
int main() {
    int arr[] = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
    int size = sizeof(arr) / sizeof(arr[0]);
    int target = 11;
    int result = binary_search(arr, size, target);
    if (result != -1) {
        printf("找到目标值 %d 在数组中的位置是： %d
", target, result);
    } else {
        printf("在数组中未找到目标值 %d
", target);
    }
    return 0;
}

相关问题与解答

1、为什么二分查找的时间复杂度是O(logn)?

答：因为每次循环后，搜索范围都会缩小一半，所以时间复杂度为对数级别。

2、如果数组中有重复元素，二分查找还能正常工作吗？

答：不能，当有重复元素时，需要修改算法来处理这种情况，一种简单的方法是在比较时同时检查两个相邻的元素是否相等，如果相等且要查找的元素比它们都大或小，则继续在相应的一侧查找；否则返回-1表示未找到。