C语言详细讲解二分查找用法 |
您所在的位置:网站首页 › c语言二分法查找数组元素 › C语言详细讲解二分查找用法 |
目录 【力扣题号】704.二分查找 力扣题目链接 示例 1: 输入: nums = [-1,0,3,5,9,12], target = 9 输出: 4 解释: 9 出现在 nums 中并且下标为 4 示例 2: 输入: nums = [-1,0,3,5,9,12], target = 2 输出: -1 解释: 2 不存在 nums 中因此返回 -1 提示: 你可以假设 nums中的所有元素是不重复的。n将在[1, 10000]之间。nums的每个元素都将在[-9999, 9999]之间。注意读题,数组为有序数组,且数组中无重复元素,因为一旦有重复元素,使用二分查找法返回的元素下标可能不是唯一的。 在二分查找的过程中,保持不变量,就是在 while 寻找中每一次边界的处理都要坚持根据区间的定义来操作,这就是循环不变量规则。 写二分法,区间的定义一般为两种,左闭右闭即 [left, right],或者左闭右开即 [left, right)。 二分法第一种写法第一种写法,我们定义 target 是在一个在左闭右闭的区间里,也就是[left, right] 。因为定义 target 在 [left, right] 区间,所以有如下两点: while (left 1); if (nums[middle] > target) { right = middle; // target 在左区间,在[left, middle)中 } else if (nums[middle] < target) { left = middle + 1; // target 在右区间,在[middle + 1, right)中 } else { // nums[middle] == target return middle; // 数组中找到目标值,直接返回下标 } } // 未找到目标值 return -1; } }; 通过以上两种方法,要注意它们不同的地方: ① right 的初始值不一样 ② 左右区间的更新值的差别 参考:《代码随想录》 到此这篇关于C语言详细讲解二分查找用法的文章就介绍到这了,更多相关C语言 二分查找内容请搜索编程学习网以前的文章希望大家以后多多支持编程学习网! |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |