当前位置：首页 > article >正文

数组-二分查找

article 2025/1/22 4:56:48

算法思想：

实践：

备注：

二分查找是一种高效的查找算法，适用于在 有序数组 或列表中快速定位目标元素的索引。

重要事情说三遍：使用前提：数组有序，无重复，如果数组未排序，先进行排序去重处理。

数组有序，无重复，如果数组未排序，先进行排序去重处理。

算法思想：

初始化左右边界： 定义两个指针 left 和 right，分别指向数组的起始位置和终止位置。
计算中间位置： 根据公式 mid = left + (right - left) // 2 计算中间位置索引，避免大数相加可能导致的溢出。（mid=（left+right）/2）这种写法当left和right很大时，可能数据溢出。

实践：

二分查找中，容易写错的地方往往是边界条件和区间的定义，这是导致程序混乱的根本原因。这里详细解释一下这两种常见的区间定义（左闭右闭 和 左闭右开）及其实现逻辑。

左闭右闭：

#include <stdio.h>

int binarySearch(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; // 未找到目标值
}

int main() {
    int arr[] = {1, 3, 5, 7, 9, 11}; // 偶数长度数组
    int size = sizeof(arr) / sizeof(arr[0]);
    int target = 7;

    int result = binarySearch(arr, size, target);
    if (result != -1) {
        printf("目标值 %d 的索引是 %d\n", target, result);
    } else {
        printf("目标值 %d 未找到。\n", target);
    }

    return 0;
}

左闭右开：

#include <stdio.h>

int search(int* nums, int numsSize, int target) {
    int left = 0;
    int right = numsSize; // 左闭右开区间
    while (left < right) { // 循环条件：left < right
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            return mid; // 找到目标值
        } else if (nums[mid] > target) {
            right = mid; // 调整右边界
        } else {
            left = mid + 1; // 调整左边界
        }
    }
    return -1; // 未找到目标值
}

int main() {
    int nums[] = {1, 3, 5, 7, 9};
    int numsSize = sizeof(nums) / sizeof(nums[0]);
    int target = 7;

    int result = search(nums, numsSize, target);
    if (result != -1) {
        printf("目标值 %d 的索引是 %d\n", target, result);
    } else {
        printf("目标值 %d 未找到。\n", target);
    }

    return 0;
}