LeetCode 34 在排序数组中查找元素的第一个和最后一个位置

二分搜索问题的学习：

  1. /*
  2.  * @lc app=leetcode.cn id=34 lang=java
  3.  *
  4.  * [34] 在排序数组中查找元素的第一个和最后一个位置?
  5.  */
  7. // @lc code=start
  8. class Solution {
  9.     public int[] searchRange(int[] nums, int target) {
  10.     if(nums.length<1)  return new int[]{-1,-1};
  11.     if(nums.length==1&&nums[0]!=target) return new int[]{-1,-1};
  12.     //首先要通过严苛条件 找左边的下界
  13.     int l=0,r = nums.length;
  14.     while(l<r){
  15.         int mid= (l+r)>>1;
  16.         //取中位索引
  17.         if(nums[mid]>=target){
  18.             r = mid;
  19.         }else{
  20.             //当mid<target的时候 left = mid+1 只会小于等于target
  21.             l =mid+1;
  22.         }
  25.     }
  26.     int left =l;
  27.         l=0;r=nums.length;
  28.         while(l<r){
  29.            int mid =(l+r)>>1;
  30.             if(nums[mid]<=target){
  31.                 l=mid+1;
  32.                 //这个时候left充当的是查找小于等于target的位置
  33.             }else{
  34.                 r = mid;
  35.                 // 这里找的是准确的右边界 r是可以保证大于target
  36.             }
  37.         }
  38.     if(r-1<left) return new int[]{-1,-1};
  39.     return new int[]{left,r-1};
  40.     }
  41. }

题目等级: 中等
要求是两端闭区间，也就是闭区间类是符合要求的元素：

第一个点： mid 计算 为 **left+(right-left)/2**可以有效避免计算溢出

以一个经典的左闭右开二分搜索为例：
每次初始的左右边界是 int left=0,right=nums.length 也就是左闭右开。

  • 对于更新状态的把握主要是在于 nums[mid] == target 时状态的更新，因为此程序更新是 left=mid+1，如果要求利用左闭右开区间的索引来获取target元素数量，也就是要求循环截止时left要在target的右边需要将最后返回来的 二分搜索上下边界 - 图1，如果要 left 在target的最后一个元素上就需要 二分搜索上下边界 - 图2 。
  • 对于左侧闭区间元素，要求在循环截止时left位于target的第一个元素处，就要在二分搜索是 nums[mid]==target 时仍然不断将 right挪到 mid的位置，如果序列中不存在目标值，target大于序列值，left左边界持续 +1 会挪到 nums.length 索引也就是边界之外，所以需要对左边界索引等于 nums.length 的结果进行处理，返回不在数组中的结果；如果小于序列值，right 会挪到0也就是元素起始的位置，如果left==0 就对left位置检查，这种情况需要检查一下left所在位置是否等于target，不等就返回不在序列内的结果，对于在序列内的情况，left会定在第一个target元素上，
  • 对于右侧开区间的二分搜索，需要保持在 nums[mid]==target 查找到target的时候也向右侧移动 left,因为使得左边界一直向target右侧第一个其他元素搜索，最终停止的位置就是target元素后面的位置