在使用二分搜索的时候，更新条件不总是相同，虽然说使用bS目的就是为了target，但也有如下几种情况：

1. 求第一个=target的索引

2. 求第一个>target的索引

3. 求第一个>=target的索引

4. 求最后一个=target的索引

5. 求最后一个<target的索引

6. 求最后一个<=target的索引

从这六种情况来看，其实可以分成两种搜索：左边界搜索->最小满足条件的索引和右边界搜索->最大满足条件的索引。这么说可能有点抽象，看1-3种情况：都是求第一个符合查询条件的索引，也就是遇到符合条件的索引就返回，即最小索引；4-6种情况：求最后一个符合查询条件的索引，即最大的符合条件的索引即最大索引。

定义查询条件为check(nums[m])接下来分两种情况讨论：

• 左边界问题：

  • 先给结论，左边界判断时，要一直收缩右侧以达到不断判断左侧数据是否符合查询条件的目的，因而当符合check条件的操作与nums[m]>t时操作相同，收缩r=m。之所以是r=m而不是r=m-1，是因为符合check条件时，此r也可能是解，所以不能跳过这个r。

  • 左边界通用代码

    int l=0,r=n-1;
    while(l<r){int m = l+(r-l)/2;if(check(m)) r = m;else l = m+1;
    }
    return l;

  • 求第一个=target的索引：

    • check为 nums[m] == target与nums[m]>target合并

    • while(l<r){int m = l+(r-l)/2;if(nums[m] >= target) r = m;else l = m+1;
      }
      return (nums[l] == target) ? l : -1;

  • 求第一个>target的索引：

    • check为nums[m] > target

    • while(l<r){int m = l+(r-l)/2;if(nums[m] > target) r = m;else l = m+1;
      }
      return l;

  • 求第一个>=target的索引：

    • check为nums[m]>=target

    • while(l<r){int m = l+(r-l)/2;if(nums[m] >= target) r = m;else l = m+1;
      }
      return l;

• 右边界问题

  • 右边界问题要求的是最大的满足条件的索引，因而要收缩左侧以达到一直判断右侧数据是否能够符合查询条件的目的。因而当符合check条件的操作与nums[m]<t时操作相同，收缩l=m。之所以是l=m而不是l=m+1，是因为符合check条件时，此l也可能是解，所以不能跳过这个l。

  • 右边界涉及到一个m向上取整的问题，也就是m每次计算m = (l+r+1)/2；原因是，右边界搜索会令l=m，若m向下取整，接近临界条件时有可能导致m=(l+r)/2=l的情况，那么再次遇上收缩，l=m。如此循环导致搜索无法跳出。

  • 右边界搜索通用代码：

    int l=0,r=n-1;
    while(l<r){int m = (r+l+1)/2;if(check(m)) l = m;else r=m-1;
    }

  • 求最后一个=target的索引

    • check为 nums[m] == target归并到nums[m] < target中

    • while(l<r){int m = (l+r+1)/2;if(nums[m] <= target) l = m;else r = m-1;
      }
      return (nums[l] == target) ? l : -1;

  • 求最后一个<target的索引

    • check为nums[m] < target

    • while(l<r){int m = (l+r+1)/2;if(nums[m] < target) l = m;else r = m-1;
      }
      return l;

  • 求最后一个<=target的索引

    • check为nums[m]<=target

    • while(l<r){int m = (l+r+1)/2;if(nums[m] <= target) l = m;else r = m-1;
      }
      return l;