学校网站模板设计,宁波做网站公司哪家好,织梦 调用网站地址,wordpress首页搭建二分查找1 二分查找的框架2 寻找一个数#xff08;基本的二分搜索#xff09;3 寻找左侧边界的二分搜索4 寻找右侧边界的二分查找5 合并二分查找场景#xff1a;有序数组寻找一个数、寻找左侧边界#xff08;有序数组第一个等目标数的下标#xff09;、寻找右侧边界#…
二分查找1 二分查找的框架2 寻找一个数基本的二分搜索3 寻找左侧边界的二分搜索4 寻找右侧边界的二分查找5 合并二分查找场景有序数组寻找一个数、寻找左侧边界有序数组第一个等目标数的下标、寻找右侧边界有序数组最后一个等于目标数的下标1 二分查找的框架
int binarySearch(int *nums,int numsSize,int target)
{int left0,rigth ...;while(...){int mid left (rigth-left)/2;if(nums[mid] target){...}else if (nums[mid]target){left ...;}else if (nums[mid]target){rigth ...;}}return ...
}使用else if是为了把所有情况写清楚这样可以清楚的展现所有细节。本文都使用else if旨在说清楚可自行简化。
其中…标记的部分就是可能出现细节问题的地方当你见到一个二分查找的代码时首先要注意这几个地方。
2 寻找一个数基本的二分搜索
这个场景是最简单的即搜索一个数如果存在返回其索引否则返回-1。
int binarySearch(int *nums,int numsSize,int target)
{int left0;int right numsSize-1; //注意while(leftrigth) //注意{int mid left (right-left)/2;if(nums[mid] target)return mid;else if(nums[mid]target){left mid1; //注意}else if(nums[mid]target){right mid1; //注意}}return -1;
}为什么while的循环条件中是而不是 答因为初始化right的赋值是numsSize-1即最后一个元素的索引而不是numsSize这二者可能出现在不同功能的二分查找中区别是前者相当于两端都闭区间[left,right]后者相当于左闭右开区间[left,right)因为索引大小为numsSize是越界的。 我们这个算法中使用的是[left,right]两端都闭的区间这个区间就是每次进行搜索的区间那while循环什么时候应该终止搜索区间为空的时候应该终止意味着你没的找了。
while(leftright)终止条件是leftright1写成区间的形式是[ right1,right]这个时候搜索区间为空直接返回-1.
while(leftright)的终止条件是leftright写成区间的形式是[right,right]者时候区间非空还有一个数nums[right]如果此时while循环停止了就漏掉一个数如果这个时候返回-1就可能出现错误。
为什么leftmid1rightmid-1 本算法的搜索区间两端都是闭的即[left,right]。那么当我们发现索引mid不是要找的target时如果确定下一步的搜索区间呢 当然是去搜索[left,mid1]或者[mid1,right]因为mid已经搜索过了应该从搜索区间去除。此算法有什么缺陷 比如说你有有序数组nums[1,2,2,2,3]此算法返回的索引是2但是如果我想得到target的左侧边界即索引1或者想得到target的右侧边界即索引3这样的话此算法是无法处理的。
3 寻找左侧边界的二分搜索
查找左侧边界的数即在一个有序数组中找到第一个等于target的下标。比如数组int nums[]{5,7,7,8,8,8,10}target8第一个等于8的下标是3第一个大于等于8的数组下标也是3。即找到第一个等于target的数等价于 找第一个大于等于targte的数的下标然后我们判断该下标所对应的数是否是target。
直接看代码
/* 二分查找左侧边界 */
int lower_bound(int *nums,int numsSize,int target)
{int left0,rightnumsSize-1,ansnumsSize;while(leftright){int mid left(right-left)/2;if(nums[mid]target){right mid-1;ans mid;}else {left mid1;}}return ans;
}
int main(void)
{int nums[]{5,7,7,8,8,8,10};int ret;//int p high_bound(nums,7,8);//printf(%d \n,p);ret lower_bound(nums,7,8);printf(%d \n,ret);return 0;
}输出是3。 当nums[mid]target时说明有大于等于target的数了我们需要更新ans来记录大于等于targte的数right需要更新然后继续往在[left,mid-1]区间找大于等于target的数如果nums[mid]target则需要在[mid1,right]区间找大于等于target的数left下标所指向的值始终是小于等于target如果全部数据全部大于targetleft将不会变化所以当结束时ans所指向的值是[left,right]区间最后一个大于等于target的值left下标所指向的值又始终是小于等于target所以ans所指向的内容是第一个大于等于target的值。
4 寻找右侧边界的二分查找
寻找右侧边界的数就是找第一个大于target的数返回其下标减1int nums[]{5,7,7,8,8,8,10}最后一个等于8的下标是5第一个大于8的数是10其下标是6减去1是5找target最后位置等价于找第一个大于target的下标减1然后判断该位置上的数是否等于target。 具体代码为
/* 二分查找右侧边界 */
int high_bound(int *nums,int numsSize,int target)
{int left0,rightnumsSize-1,ansnumsSize;while(leftright){int mid left(right-left)/2;if(nums[mid]target){right mid-1;ans mid;}else {left mid1;}}return ans;
}
int main(void)
{int nums[]{5,7,7,8,8,8,10};int ret;//int p high_bound(nums,7,8);//printf(%d \n,p);ret high_bound(nums,7,8)-1;printf(%d \n,ret);return 0;
}运行结果是5。 如果nums[mid]target有大于target的数了ans就要去记录right更新rightmid-1 如果nums[mid]target则left需要更新leftmid-1left指示的内容始终是小于等于target的如果数据全部大于targetleft不会变。只要leftright就会一直缩小区间当运行结束后ans所指示的内容是最后一个大于target的数。
5 合并
我们添加一个参数表示找第一个等于target的数还是找最后一个等于target的数。
int binarySearch(int* nums, int numsSize, int target, bool lower) {int left 0, right numsSize - 1, ans numsSize;while (left right) {int mid (left right) / 2;if (nums[mid] target || (lower nums[mid] target)) {right mid - 1;ans mid;} else {left mid 1;}}return ans;
}当lower为真时表示找第一个大于等于target的数当lowe为假时表示找第一个大于target的数返回之后检查和上面代码一样。
leedcode的第34题在排序数组中查找元素的第一个和最后一个位置
示例代码 /*
在一个升序数组中找第一个等于target的数组即找第一个大于等于target的数返回其下标最后判断
是否等于targettarget。
找最后一个等于target的数组即找第一个大于target的数返回其下标减1最后判断该下标对应的数是否等于target。
*/
int binarySearch(int *nums,int numsSize,int target,bool lower)
{int left0,rightnumsSize-1,ansnumsSize;while(leftright){int midleft(right-left)/2;if(nums[mid]target || (lower nums[mid]target)){rightmid-1;ans mid;}else{leftmid1;}}return ans;
}
/*** Note: The returned array must be malloced, assume caller calls free().*/
int* searchRange(int* nums, int numsSize, int target, int* returnSize){int leftIdx binarySearch(nums,numsSize,target,true);int rightIdx binarySearch(nums,numsSize,target,false)-1;int *ret (int *)malloc(sizeof(int)*2);*returnSize2;if(leftIdxrightIdx nums[leftIdx]target nums[rightIdx]target){ret[0]leftIdx;ret[1]rightIdx;return ret;}ret[0]-1;ret[1]-1;return ret;
}
