国内最好的网站建设公司,有什么免费的wordpress,网站联盟如何实现,网站脚本错误决定我们成为什么样人的#xff0c;不是我们的能力#xff0c;而是我们的选择。——《哈利波特与密室》二分查找是查找算法里面是很优秀的一个算法#xff0c;特别是在有序的数组中#xff0c;这种算法思想体现的淋漓尽致。一.题目描述及其要求请实现无重复数字的升序数组的…决定我们成为什么样人的不是我们的能力而是我们的选择。——《哈利·波特与密室》二分查找是查找算法里面是很优秀的一个算法特别是在有序的数组中这种算法思想体现的淋漓尽致。一.题目描述及其要求请实现无重复数字的升序数组的二分查找给定一个 元素升序的、无重复数字的整型数组 arr和一个目标值 target 写一个函数搜索 arr中的 target如果目标值存在返回下标下标从 0 开始否则返回 -1.示例一输入[-1,0,3,4,6,10,13,14],13
返回值6
说明13 出现在arr中并且下标为 6 示例二输入[],3
返回值-1
说明arr为空返回-1 示例三输入[-1,0,3,4,6,10,13,14],2
返回值-1
说明2 不存在arr中因此返回 -1 二.分治思想分治即“分而治之”,“分”指的是将一个大而复杂的问题划分成多个性质相同但是规模更小的子问题子问题继续按照这样划分直到问题可以被轻易解决“治”指的是将子问题单独进行处理。经过分治后的子问题需要将解进行合并才能得到原问题的解因此整个分治过程经常用递归来实现。1.逐个遍历思路本来我们可以遍历数组直接查找每次检查当前元素是不是要找的值。for(int i 0; i length; i)if(arr[i] target)return i;2.逐个遍历出现的问题但是这样这个有序的数组我们就没有完全利用起来。我们想想若是目标值比较小肯定在前半区间若是目标值比较大肯定在后半区间怎么评价大小我们可以用中点值作为一个标杆将整个数组分为两个区间目标值与中点值比较就能知道它会在哪个区间这就是分治的思维。三分治思想具体做法step 1从数组首尾开始每次取中点值。step 2如果中间值等于目标即找到了可返回下标如果中点值大于目标说明中点以后的都大于目标因此目标在中点左半区间如果中点值小于目标则相反。step 3根据比较进入对应的区间直到区间左右端相遇意味着没有找到代码实现int search(int*arr, int length, int target ) {if(length 0) return -1;int left0, rightlength-1;while(leftright) {int mid left(right-left)/2;if(arr[mid]target) return mid;if(arr[mid]target) leftmid1;if(arr[mid]target) rightmid-1;}return -1;
}psint mid left(right-left)/2;与int mid(leftright)/2是一样的但是选择前者更安全因为后者两个整数相加数据过于庞大可能会出现数据溢出的情况所以采用前者更加可靠。 也可以这样写mid left(right-left 1); -大于位移运算的优先级 左移*2 本算法到这其实二分查找可以分为几种情况来讨论这里提供一种比较好理解的方案具体算法大家可以参考相应资料自了解大家加油。。。。。最近在做算法题目可以关注我点个赞有问题可以一起讨论。以后的几篇文章都讲解算法的题目。
