二分查找法实例应用的细节分析

细节二搜索时选定新边界新边界的值是mid ± 1还是mid在进行一次搜索判断之后查找新边界时新边界一般有两种选择以right为例right mid - 1right mid按照标准的二分查找框架这两种赋值方式的区别是新区间是否还要包括mid这个点。一般来说选择新边界时其实已经对mid这个值已经判断过了秉持着最大程度地缩小搜索区间的理念按理说应该要将mid这个点在新区间排除掉的但联系上一个问题如果判断条件是left right那么搜索区间是左闭右开区间即使right mid也不会判断mid但是如果right mid - 1那么就会少判断right mid - 1这个点所以这里新区间的边界为right mid。所以这里的缩小区间表示式是和判断条件联系在一起的需要考虑实际情况然后再进行判断尽管二分查找有统一的框架模板操作步骤但二分查找不是一种框架模板而是一种思想案例当数组中含有多个目标数字查找最左边目标数字的索引查找最右边目标数字的索引2. 当数组中不含有目标数字查找目标数字的插入位置搜索边界集合中含有多个符合要求的解查找左边界或者右边界e.g.按照全闭区间查找查找左右边界的关键是nums[mid] target时如何划定新区间。如果查找左边界int binarySearch(vectorint nums,int target) { int n nums.size(); int left 0,right n - 1; int ans -1; while(left right){ int mid left (right - left) / 2; if (nums[mid] target){ // 这里能判断出 mid 可能是左边界但是对于 mid - 1 我们是无法判断的所以 ans mid; right mid - 1; }else if (nums[mid] target) { right mid - 1; }else { left mid 1; } } return ans; }最终结果都是ans。在每一次判断(nums[mid] target)中我们只能判断出mid是符合要求的而无法判断出mid - 1或者mid 1是否符合要求所以ans mid。按照这个思路中其实也可以不采用 ans 这个变量而采用right 1或者left - 1的形式因为right 1或者left - 1等于mid不过这需要进一步判断right 1或者left - 1是否在数组范围内如果你将nums[mid] target和nums[mid] target或者nums[mid] target合并起来你还需要判断nums[left - 1]或者nums[right 1]是否等于target因为当nums[mid] target或者nums[mid] target时也会给ans赋值。