数组-二分查找

目录

算法思想：

实践：

备注：

---

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

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

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

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

算法思想：

1. 初始化左右边界： 定义两个指针 left 和 right，分别指向数组的起始位置和终止位置。
2. 计算中间位置： 根据公式 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 < rightint 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;
}

备注：

在二分查找中，左中点（向下取整） 和 右中点（向上取整） 的计算方式会影响算法的细节，但在实际应用中，它们的功能基本是等效的。