C语言每日一题（6）二分查找
思路分析
1.二分查找的基本思想
二分查找的基本思想是通过比较中间元素与目标元素的大小来不断缩小搜索范围，直到找到目标元素或确定目标元素不存在为止。其基本步骤如下：
1. 确定搜索范围：对于有序的数组或列表，选择开始和结束的索引，将其定义为搜索范围的边界。
2. 计算中间元素：通过取开始和结束索引的中间位置，计算中间元素的索引。
3. 比较目标元素：将中间元素与目标元素进行比较。
- 如果中间元素等于目标元素，则找到了目标元素，搜索结束。 - 如果中间元素小于目标元素，则目标元素必然在中间元素的右侧，更新搜索范围的开始索引为中间元素的右边一位。 - 如果中间元素大于目标元素，则目标元素必然在中间元素的左侧，更新搜索范围的结束索引为中间元素的左边一位。
4. 重复步骤2和步骤3，在新的搜索范围内进行二分查找，直到找到目标元素或确定目标元素不存在为止。如果搜索范围为空，即开始索引大于结束索引，则目标元素不存在。
二分查找的关键在于每次通过比较中间元素来确定目标元素的可能位置，将搜索范围缩小一半，从而大大减少了搜索的次数，提高了查找效率。但前提是数组或列表必须是有序的。
2.代码实现
int search(int* nums, int numsLen, int target ) {
if (numsLen <= 0)return -1;
int low = 0, high = numsLen - 1; //初始化双指针
int mid = (low + high) / 2;
while (target != nums[mid] &&
low <= high) { //若当前mid值不为查找值，更新查找区域。
if (target > nums[mid]) {
low = mid + 1;
mid = (low + high) / 2;
} else {
high = mid - 1;
mid = (low + high) / 2;
}
}
if (low > high)return -1;
else return mid;
}本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2024-01-23，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录