在使用二分搜索的時候，更新條件不總是相同，雖然說使用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;