做水果生意去那个网站,专业做淘宝网站,惠州网络推广,中国最厉害的室内设计师目录
算法思想#xff1a;
实践#xff1a;
备注#xff1a; 二分查找是一种高效的查找算法#xff0c;适用于在 有序数组 或列表中快速定位目标元素的索引。
重要事情说三遍#xff1a;使用前提#xff1a;数组有序#xff0c;无重复#xff0c;如果数组未排序
实践
备注 二分查找是一种高效的查找算法适用于在 有序数组 或列表中快速定位目标元素的索引。
重要事情说三遍使用前提数组有序无重复如果数组未排序先进行排序去重处理。 数组有序无重复如果数组未排序先进行排序去重处理。 数组有序无重复如果数组未排序先进行排序去重处理。
算法思想
初始化左右边界 定义两个指针 left 和 right分别指向数组的起始位置和终止位置。计算中间位置 根据公式 mid left (right - left) // 2 计算中间位置索引避免大数相加可能导致的溢出。midleftright/2这种写法当left和right很大时可能数据溢出。
实践
二分查找中容易写错的地方往往是边界条件和区间的定义这是导致程序混乱的根本原因。这里详细解释一下这两种常见的区间定义左闭右闭 和 左闭右开及其实现逻辑。
左闭右闭
#include stdio.hint 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.hint 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;
}备注
在二分查找中左中点向下取整 和 右中点向上取整 的计算方式会影响算法的细节但在实际应用中它们的功能基本是等效的。
