本文共 2591 字，大约阅读时间需要 8 分钟。

查找大于等于/大于key的第一个元素

这种通常题目描述为满足某种情况的最小的元素。

int left = 1,right = n;    while(left < right)    {           //这里不需要加1。我们考虑如下的情况，最后只剩下A[i],A[i + 1]。        //首先mid = i，如果A[mid] > key，那么right = left = i，跳出循环，如果A[mid] < key，left = right = i + 1跳出循环，所有不会死循环。        int mid = (left + right) / 2;        if(A[mid] > key)//如果要求大于等于可以加上等于，也可以是check(A[mid])            right = mid;        //因为找的是大于key的第一个元素，那么比A[mid]大的元素肯定不是第一个大于key的元素，因为A[mid]已经大于key了，所以把mid+1到后面的排除        else            left = mid + 1;        //如果A[mid]小于key的话，那么A[mid]以及比A[mid]小的数都需要排除，因为他们都小于key。不可能是第一个大于等于key的元素，    }

查找小于等于/小于key的最后一个元素

这种通常题目描述为满足某种情况的最大的元素。如Leetcode69题，求sqrt(x)向下取整就是这种模板。

int left = 1, right = n;    while(left < right)    {           //这里mid = (left + right + 1) / 2;        //考虑如下一种情况，最后只剩下A[i],A[i + 1]，如果不加1，那么mid = i，如果A[mid] < key，执行更新操作后，left = mid，right = mid + 1，就会是死循环。        //加上1后，mid = i + 1,如果A[mid] < key，那么left = right = mid + 1,跳出循环。如果A[mid] > key，left = mid = i，跳出循环。        int mid = (left + right + 1) / 2;        if(A[mid] < key)            left = mid;//如果A[mid]小于key，说明比A[mid]更小的数肯定不是小于key的最大的元素了，所以要排除mid之前的所有元素        else            right = mid - 1;//如果A[mid]大于key，那么说明A[mid]以及比A[mid]还要大的数都不可能小于key，所以排除A[mid]及其之后的元素。    }

class Solution:    def hIndex(self, citations):        """        :type citations: List[int]        :rtype: int        """        n = len(citations)        left, right = 0, n - 1        while left <= right:            pivot = left + (right - left) // 2            if citations[pivot] == n - pivot:                return n - pivot            elif citations[pivot] < n - pivot:                left = pivot + 1            else:                right = pivot - 1                return n - left

套模板

class Solution:    def hIndex(self, citations: List[int]) -> int:        # 查找大于等于key的第一个元素        left = 0        right = len(citations) - 1        while left < right:            mid = (left + right) // 2            if len(citations) - mid == citations[mid]:                return citations[mid]            elif len(citations) - mid > citations[mid]:                left = mid + 1            else:                ans.append(len(citations) - mid)                right = mid        return left

套模板

class Solution:    def mySqrt(self, x: int) -> int:        # 查找小于等于key的最后一个元素模板：        left = 0        right = x // 2 + 1        while left < right:            mid = (left + right + 1) // 2            if mid ** 2 == x:                return mid            elif mid ** 2 < x:                left = mid            else:                right = mid - 1        return left