C语言二分查找算法实现及代码解释

#include <stdio.h>

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

int main() {
    int arr[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    int x;
    scanf("%d", &x);
    int index = binarySearch(arr, 10, x);
    if (index != -1) {
        printf("Index is %d\n", index);
    } else {
        printf("Not Found\n");
    }
    return 0;
}

解释:

1. 定义binarySearch函数: 该函数接受三个参数：

   • arr: 要查找的排序数组
   • n: 数组的长度
   • x: 要查找的数值 函数使用二分查找法在数组中查找 x，并返回 x 的索引，如果未找到则返回 -1。

2. 二分查找算法:

   • 初始化 left 和 right 分别指向数组的第一个元素和最后一个元素的索引。
   • 循环执行直到 left 大于 right。
   • 计算中间索引 mid。
   • 如果 arr[mid] 等于 x，则找到了目标元素，返回 mid。
   • 如果 arr[mid] 小于 x，则说明目标元素在 mid 的右侧，将 left 更新为 mid + 1。
   • 如果 arr[mid] 大于 x，则说明目标元素在 mid 的左侧，将 right 更新为 mid - 1。

3. main 函数:

   • 定义一个长度为 10 的有序数组 arr 并初始化。
   • 从用户输入读取一个整数 x。
   • 调用 binarySearch 函数，传入 arr、数组长度和 x。
   • 根据函数返回值判断是否找到目标元素，并打印相应结果。

示例:

假设数组 arr 为 {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}。

输入: 8 输出: Index is 7

输入: 12 输出: Not Found