建设网站用什么时候开始,6种常见的网页布局类型,公众号排名优化软件,移商网站建设一:问题描述
当我们在用二分法查找元素的时候#xff0c;我们往往特希望遇到是奇数个元素个数的数组#xff0c;因为划分完左右两边的个数相等#xff0c;所以在以前刚学二分法的时候就有这个疑问#xff0c;当时就是模模糊糊过去了#xff0c;再遇到其实还是会有疑问。现…一:问题描述
当我们在用二分法查找元素的时候我们往往特希望遇到是奇数个元素个数的数组因为划分完左右两边的个数相等所以在以前刚学二分法的时候就有这个疑问当时就是模模糊糊过去了再遇到其实还是会有疑问。现在实例验证遇见偶数个数数组元素个数时的二分法
二思路示例
目标查询数组当中是否存在某个数存在返回其下标不存在返回-1
思路1.这是一个很典型的二分查找的例子但关键的是我们要考虑其中的符号问题 2.也就是左闭右闭左闭右开左开右闭这是二分法的重点 3.我们一般使用的是左闭右闭即[left,right], 举例如 输入偶数个的数组array[7]: 我们想要查询29是否存在 1 5 9 11 23 29 31 50 1:我们在选取middle时 middle 7/2 3 取下标为3的元素也就是112:这时划分的数组左右长度不一样跟我们常规的奇数个的时候不一样这时我们对左右两边个数的考虑是多余的,因为我们每次都是将middle左边右边的所有元素均排除跟个数完全没有关系3:回到上方的例子当中我们比较29和11的时候直接将左边的所有元素pass掉 下一次比较[middle1,right]当中的元素这里左右两边均取闭区间即左闭右闭 三上码
/**目标查询数组当中是否存在某个数存在返回其下标不存在返回-1思路1.这是一个很典型的二分查找的例子但关键的是我们要考虑其中的符号问题2.也就是左闭右闭左闭右开左开右闭这是二分法的重点3.我们一般使用的是左闭右闭即[left,right],举例如输入偶数个的数组array[7]: 我们想要查询29是否存在 1 5 9 11 23 29 31 50 1:我们在选取middle时 middle 7/2 3 取下标为3的元素也就是112:这时划分的数组左右长度不一样跟我们常规的奇数个的时候不一样这时我们对左右两边个数的考虑是多余的,因为我们每次都是将middle左边右边的所有元素均排除跟个数完全没有关系3:回到上方的例子当中我们比较29和11的时候直接将左边的所有元素pass掉 下一次比较[middle1,right]当中的元素这里左右两边均取闭区间即左闭右闭 **/ #includebits/stdc.h
using namespace std;int find(int a[],int size,int target){int left 0;int right size - 1;//因为采用的左闭右闭比如a[5],那么左右边界就是[0,4] int mid;while(left right){ //当left right时候 左闭右闭依然有效mid left (right - left)/2;//这里等价于 right left/2if(a[mid] target){right mid - 1;}else if (a[mid] target){left mid 1;}else{return mid;}}return -1;//没找到 }int main(){int a[10];int N,target;//N个数和要查询的数 cin N target;for(int i 0; i N; i){cin a[i];} int res find(a,N,target);cout res; } 四:补充左闭右开
1:左闭右开[left,right)
即相应的while条件中left right 而当a[mid] target;时候对应的 right mid
上码
int search(int nums[], int size, int target)
{int left 0;int right size; //定义target在左闭右开的区间里即[left, right)while (left right) { //因为left right的时候在[left, right)区间上无意义int middle left ((right - left) / 2);if (nums[middle] target) {right middle; //target 在左区间在[left, middle)中 } else if (nums[middle] target) {left middle 1;} else {return middle;}} // 没找到就返回-1return -1;
}
参考自
