本系列为Leetcode刷题笔记，刷题平台为Leetcode中文站，刷题按Tag分类。本系列题解汇总如下 (持续更新…)：

本文主要是二分查找相关题目题解总结。

[TOC]

二分查找

二分查找也称折半查找，它是一种效率较高的查找方法。但是折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排序。

查找过程

二分查找适用于有序的顺序表。首先将表中间位置记录的关键字和查找关键字比较；如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表；如果中间位置记录的关键字大于查找关键字，则进入前一子表，否则进入后一子表；重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止。

算法要求

必须采用顺序存储结构；
必须按关键字大小有序排序。

复杂度

时间复杂度O(log2n)，空间复杂度为O(1)。

中值mid的计算

有两种计算中值mid的方式：

mid = (left+right) // 2;
mid = left + (right-left)//2
left+right 可能出现加法溢出，最好使用第二种方式。

返回值

如果成功查找到key：

返回key所在的位置。
如果循环退出时仍然没有找到key，表示查找失败，有两种可能返回值：

-1:以一个错误码表示没有查找到key；
pos：将key插入到原列表中合适的位置。

正常实现

class Solution(object):
    def binarySearch(self, nums, key):
        if len(nums) == 0:
            return -1
        left, right = 0, len(nums)-1
        while left <= right:
            mid = left + (right-left)//2
            if nums[mid] == key:
                return mid
            elif nums[mid] > key:
                right = mid - 1
            else:
                left  = mid + 1
        return -1

二分查找的变种

二分查找可以有很多变种，变种实现要注意边界值的判断。例如在一个有重复元素的数组中查找 key 的最左位置的实现如下：

class Solution(object):
    def binarySearch(self, nums, key):
        if len(nums) == 0:
            return -1
        left, right = 0, len(nums)-1
        while left < right: # 小于 而不是小于等于
            mid = left + (right-left)//2
            if nums[mid] >= key:
                right = mid # mid 不是mid-1
            else:
                left  = mid + 1
        return left
if __name__ == '__main__':
    result = Solution().binarySearch([1,1,1,2,3,3,4,5,6,7],1)
    print(result)

与正常实现不同：

right 的赋值表达式为 right = mid；
循环条件为left<right;
最后返回left而不是-1。

解释：

在nums[mid] >= key的情况下，可以推导出最左key位于[left,mid]区间中，right 的赋值表达式为 right = mid，因为mid位置也可能为解；
在right 的赋值表达式为 right = mid的情况下，如果循环条件为left<=right，将会导致陷入死循环的情况；
当循环退出时，不表示没有查找成功，为了验证有没有查找到，应该在调用函数时判断一下返回值上的值和key是否相等。

29. 两数相除

题目描述

给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。

返回被除数 dividend 除以除数 divisor 得到的商。

示例 1:

1 2	输入: dividend = 10, divisor = 3 输出: 3

示例 2:

1 2	输入: dividend = 7, divisor = -3 输出: -2

说明:

1
2
3

被除数和除数均为 32 位有符号整数。
除数不为 0。
假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−231,  231 − 1]。本题中，如果除法结果溢出，则返回 231 − 1。

解题思路

通过位运算模拟乘2的操作，加快扩大divisor的速度。
使用两层while，外层用来控制最终跳出循环，同时初始化逼近的间隔；内层通过不断的乘2用来加快逼近速度。属于二分查找的变种。

class Solution(object):
    def divide(self, dividend, divisor):
        """
        :type dividend: int
        :type divisor: int
        :rtype: int
        """
        if divisor == 0:
            return False
        
        flag = (dividend < 0) is (divisor < 0)
        dividend, divisor = abs(dividend), abs(divisor)
        
        if dividend < divisor:
            return 0
        
        res = 0
        while dividend >= divisor:
            temp = divisor
            count = 1
            while dividend >= temp:
                dividend -= temp
                res += count
                temp = temp << 1
                count = count << 1
        
        if not flag:
            res = -res
        if res > 2**31-1:
            return 2**31-1
        if res < -2**31:
            return -2**31
        return res

class Solution {
    public int divide(int dividend, int divisor) {

        int flag = 1;
        if ((dividend<0) != (divisor<0))
            flag = -1;
        long newDividend = Math.abs((long) dividend);
        long newDivisor = Math.abs((long) divisor);

        long res = 0;
        while (newDividend >= newDivisor){
            long count = 1;
            long tempDivisor = newDivisor;
            while (tempDivisor <= newDividend){
                res += count;
                newDividend -= tempDivisor;
                tempDivisor <<= 1;
                count <<= 1;
            }
        }
        if (flag == -1)
            res = -res;
        if (res < Integer.MIN_VALUE || res > Integer.MAX_VALUE)
            return Integer.MAX_VALUE;
        return (int)res;
    }
}

public class Main {

    public static void main(String[] args) {
        Solution sol = new Solution();
        int res = sol.divide(-2147483648,                -1);
        System.out.println(res);
    }
}

一层循环超出时间限制

class Solution(object):
    def divide(self, dividend, divisor):
        """
        :type dividend: int
        :type divisor: int
        :rtype: int
        """

        if dividend == 0:
            return 0
        
        flag = 1 if (dividend < 0) is (divisor < 0) else -1
        dividend, divisor = abs(dividend), abs(divisor)
        
        res = 0
        while dividend >= divisor:
            res += 1
            dividend -= divisor
        
        res = res*flag
        if res > 2**31-1:
            return 2**31-1
        if res < -2**31:
            return -2**31
        return res

33. 搜索旋转排序数组

题目描述

假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。

搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。

你可以假设数组中不存在重复的元素。

你的算法时间复杂度必须是 O(log n) 级别。

示例 1:

1 2	输入: nums = [4,5,6,7,0,1,2], target = 0 输出: 4

示例 2:

1 2	输入: nums = [4,5,6,7,0,1,2], target = 3 输出: -1

解题思路

双指针。

当nums[mid] == target时，返回mid；
当nums[mid] < nums[right]，则[mid,right]一定有序，判断target是否在(mid,right]中，如果在则left = mid+1，否则在另一段中，right = mid-1
当nums[mid] > nums[right]，则[left,mid]一定有序，判断target是否在[left,mid)中，如果在，则right=mid-1，否则，left = mid+1.

class Solution(object):
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        if len(nums) == 0:
            return -1
        
        left, right = 0, len(nums)-1
        while left <= right:
            mid = left + (right-left)//2
            if nums[mid] == target:
                return mid
            
            if nums[mid] < nums[right]:
                if target > nums[mid] and target <= nums[right]:
                    left = mid+1
                else:
                    right = mid-1
            else:
                if target >= nums[left] and target < nums[mid]:
                    right = mid-1
                else:
                    left = mid+1
        
        return -1

class Solution(object):
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        
        if len(nums) == 0:
            return -1
        
        left, right = 0, len(nums)-1
        
        while left <= right:
            mid = left+(right-left)//2
            if nums[mid] == target:
                return mid
            
            if nums[mid] <= nums[right]:
                if nums[mid] < target <= nums[right]:
                    left = mid + 1
                else:
                    right = mid - 1
            elif nums[mid] >= nums[left]:
                if nums[left] <= target < nums[mid]:
                    right = mid - 1
                else:
                    left = mid + 1
        
        return -1

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

题目描述

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

你的算法时间复杂度必须是 O(log n) 级别。

如果数组中不存在目标值，返回 [-1, -1]。

示例 1:

输入: nums = [5,7,7,8,8,10], target = 8
输出: [3,4]
示例 2:

输入: nums = [5,7,7,8,8,10], target = 6
输出: [-1,-1]

解题思路

二分查找。

当nums[mid] == target时，说明target在数组中的[left,right]中，其中开始位置在[left,mid]，结束位置在[mid,right]中；
- 从头遍历[left,mid]，找到第一个等于target的位置作为开始位置；
- 从后遍历[mid,right]，从后找到第一个等于target的位置作为结束位置；
当nums[mid] > target时，right = mid-1
当nums[mid] < target时，left = mid+1

class Solution(object):
    def searchRange(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        if len(nums) == 0:
            return [-1,-1]
        left, right = 0 ,len(nums)-1
        while left <= right:
            mid = left + (right-left)//2
            if nums[mid] == target:
                temp = []
                for i in range(left,mid+1):
                    if nums[i] == target:
                        temp.append(i)
                        break
                for i in range(right, mid-1,-1):
                    if nums[i] == target:
                        temp.append(i)
                        break
                return temp
            elif nums[mid]  > target:
                right = mid - 1
            else:
                left = mid + 1
        return [-1,-1]
if __name__ == '__main__':
    result = Solution().searchRange([5,7,7,8,8,10],8)
    print(result)

35. 搜索插入位置

题目描述

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

你可以假设数组中无重复元素。

示例 1:

1 2	输入: [1,3,5,6], 5 输出: 2

示例 2:

1 2	输入: [1,3,5,6], 2 输出: 1

示例 3:

1 2	输入: [1,3,5,6], 7 输出: 4

示例 4:

1 2	输入: [1,3,5,6], 0 输出: 0

解题思路

class Solution(object):
    def searchInsert(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        
        if len(nums) == 0:
            return 0
        
        left, right = 0, len(nums)-1
        
        while left <= right:
            mid = left+(right-left)//2
            if nums[mid] == target:
                return mid
            elif nums[mid] > target:
                right = mid - 1
            else:
                left = mid + 1
        
        return left

50. Pow(x, n)

题目描述

实现 pow(x, n) ，即计算 x 的 n 次幂函数。

示例 1:

1 2	输入: 2.00000, 10 输出: 1024.00000

示例 2:

1 2	输入: 2.10000, 3 输出: 9.26100

示例 3:

1
2
3

输入: 2.00000, -2
输出: 0.25000
解释: 2-2 = 1/22 = 1/4 = 0.25

说明:

1 2	-100.0 < x < 100.0 n 是 32 位有符号整数，其数值范围是 [−231, 231 − 1] 。

解题思路

直接乘，超时。

class Solution(object):
    def myPow(self, x, n):
        """
        :type x: float
        :type n: int
        :rtype: float
        """
        if x == 0.0:
            return 0
        if n == 0:
            return 1.0
        
        flag = (n < 0)
        n = abs(n)
        
        res = 1
        while n > 0:
            res *= x
            n -= 1
        
        if flag:
            res = 1.0/res
        return res

二分求幂，递归。

如果n=0，返回1；
如果n为负数，相当于求(1.0/x)^(-n)。
如果n为正奇数，相当于求 x (x^2)^(n//2)；
如果n为正偶数，相当于求 (x^2)^(n//2)。

class Solution(object):
    def myPow(self, x, n):
        """
        :type x: float
        :type n: int
        :rtype: float
        """
        if n == 0:
            return 1.0
        elif n < 0:
            return 1.0 / self.myPow(x, -n)
        elif n % 2 == 1:
            # return self.myPow(x*x, n//2) * x
            return self.myPow(x, n-1) * x
        else:
            return self.myPow(x*x, n//2)

二分求幂，迭代。

class Solution(object):
    def myPow(self, x, n):
        """
        :type x: float
        :type n: int
        :rtype: float
        """
        if n == 0:
            return 1.0
        
        flag = (n<0)
        n = abs(n)
        
        res = 1
        while n:
            if n%2 == 1:
                res *= x
            n >>= 1
            x *=x
        if flag:
            res = 1.0/res
        return res

69. x 的平方根

题目描述

实现 int sqrt(int x) 函数。
计算并返回 x 的平方根，其中 x 是非负整数。
由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

示例 1:

输入: 4
输出: 2
示例 2:

输入: 8
输出: 2
说明: 8 的平方根是 2.82842…, 由于返回类型是整数，小数部分将被舍去。

解题思路

二分查找。一个数x的开根号一定在[1,x//2+1]之间，因为在(x//2+1)^2 > x，所以我们将二分查找的终点设为x//2+1;
对于 x = 8，它的开方是 2.82842…，最后应该返回 2 而不是 3。在循环条件为 left <= right 并且循环退出时，right 总是比 left 小 1，也就是说 right = 2，left = 3，因此最后的返回值应该为 right 而不是 left。

class Solution(object):
    def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        """
        if x == 0:
            return 0
        if x == 1:
            return 1
        left, right = 1, x//2+1
        while left <= right:
            mid = left + (right - left) // 2
            if mid * mid == x:
                return mid
            elif mid * mid > x:
                right = mid - 1
            else:
                left = mid + 1
        return right

74. 搜索二维矩阵

题目描述

编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：

每行中的整数从左到右按升序排列。
每行的第一个整数大于前一行的最后一个整数。

示例 1:

输入:
matrix = [
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]
target = 3
输出: true

示例 2:

输入:
matrix = [
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]
target = 13
输出: false

解题思路

从左下角开始搜索

class Solution(object):
    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        if len(matrix) == 0:
            return False
        
        rows, cols = len(matrix)-1, len(matrix[0])-1
        i, j = rows, 0
        
        while i >= 0 and j <= cols:
            if matrix[i][j] == target:
                return True
            elif matrix[i][j] > target:
                i -= 1
            else:
                j += 1
        
        return False

81. 搜索旋转排序数组 II

题目描述

假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如，数组 [0,0,1,2,2,5,6] 可能变为 [2,5,6,0,0,1,2] )。

编写一个函数来判断给定的目标值是否存在于数组中。若存在返回 true，否则返回 false。

示例 1:

1 2	输入: nums = [2,5,6,0,0,1,2], target = 0 输出: true

示例 2:

1 2	输入: nums = [2,5,6,0,0,1,2], target = 3 输出: false

进阶:

这是搜索旋转排序数组的延伸题目，本题中的 nums 可能包含重复元素。
这会影响到程序的时间复杂度吗？会有怎样的影响，为什么？

解题思路

在正式比较之前，先移动左指针，使它指向和右指针不同的数字上。

class Solution(object):
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: bool
        """
        
        if len(nums) == 0:
            return False
        
        left, right = 0, len(nums)-1
        while left <= right:
            
            while left < right and nums[left] == nums[right]:
                left += 1
                
            mid = left + (right-left)//2
            if nums[mid] == target:
                return True
            
            if nums[mid] <= nums[right]:
                if nums[mid] < target <= nums[right]:
                    left = mid + 1
                else:
                    right = mid - 1
            elif nums[mid] >= nums[left]:
                if nums[left] <= target < nums[mid]:
                    right = mid - 1
                else:
                    left = mid + 1
            
        return False

153. 寻找旋转排序数组中的最小值

题目描述

假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。

请找出其中最小的元素。

你可以假设数组中不存在重复元素。

示例 1:

输入: [3,4,5,1,2]
输出: 1
示例 2:

输入: [4,5,6,7,0,1,2]
输出: 0

解题思路

数组分为两个升序的数组，使用二分查找。

当nums[mid]>nums[mid+1]时，最小值为nums[mid+1];
当nums[mid]>nums[right]时,left = mid+1;
当nums[mid]>nums[right]时,right = mid，因为mid位置可能就是最小值了；
由于right = mid，则循环条件为left<right。

class Solution(object):
    def findMin(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if len(nums) == 0:
            return 0
        if len(nums) == 1:
            return nums[0]
        left, right = 0, len(nums)-1
        while left < right:
            mid = left + (right-left)//2
            if mid+1 <= len(nums)-1 and nums[mid] > nums[mid+1]:
                return nums[mid+1]
            if nums[mid] > nums[right]:
                left = mid + 1
            else:
                right = mid
        return nums[left]
if __name__ == '__main__':
    result = Solution().findMin([4,5,6,7,0,1,2])
    print(result)

二刷

class Solution(object):
    def findMin(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if len(nums) == 0:
            return 0
        
        left, right = 0, len(nums)-1
        
        while left <= right:
            mid = left + (right-left)//2
            if mid-1>=0 and nums[mid-1] > nums[mid]:
                return nums[mid]
            
            if nums[mid] <= nums[right]:
                right = mid-1
            else:
                left = mid + 1
        
        return nums[left]

162. 寻找峰值

题目描述

峰值元素是指其值大于左右相邻值的元素。

给定一个输入数组 nums，其中 nums[i] ≠ nums[i+1]，找到峰值元素并返回其索引。

数组可能包含多个峰值，在这种情况下，返回任何一个峰值所在位置即可。

你可以假设 nums[-1] = nums[n] = -∞。

示例 1:

1
2
3

输入: nums = [1,2,3,1]
输出: 2
解释: 3 是峰值元素，你的函数应该返回其索引 2。

示例 2:

输入: nums = [1,2,1,3,5,6,4]
输出: 1 或 5 
解释: 你的函数可以返回索引 1，其峰值元素为 2；
     或者返回索引 5， 其峰值元素为 6。

说明:

你的解法应该是 O(logN) 时间复杂度的。

解题思路

用两个mid，判断上坡还是下坡，上坡将left移到坡顶，下坡将right移到坡顶

class Solution(object):
    def findPeakElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        
        
        if len(nums) <= 1:
            return 0
        
        left, right = 0, len(nums)-1
        while left < right:
            mid1 = left+(right-left)//2
            mid2 = mid1 + 1
            if nums[mid1] < nums[mid2]:
                left = mid2
            else:
                right = mid1
        
        return left

278. 第一个错误的版本

题目描述

你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。

假设你有 n 个版本 [1, 2, …, n]，你想找出导致之后所有版本出错的第一个错误的版本。

你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。

示例:

给定 n = 5，并且 version = 4 是第一个错误的版本。
调用 isBadVersion(3) -false
调用 isBadVersion(5) -true
调用 isBadVersion(4) -true
所以，4 是第一个错误的版本。

解题思路

给定 n = 5，并且 version = 4 是第一个错误的版本时，输入分布为[1,2,3,4,5]，对应版本正误情况为[0,0,0,1,1]，题目要求出最靠左的1的位置。
使用二分查找：

如果第mid个版本出错，则第一个出错版本在[left,mid]，有可能出现在mid位置，因此right = mid；
如果第mid个版本没错，则第一个出错版本在[mid+1,right]，因此left = mid+1;
当循环条件为left<=right时，会陷入死循环。

总结：当right的赋值表达式为 right = mid 时，循环条件为 left < right。

# The isBadVersion API is already defined for you.
# @param version, an integer
# @return a bool
def isBadVersion(version):
    if version in (1,2,3):
        return False
    elif version in (4,5):
        return True

class Solution(object):
    def firstBadVersion(self, n):
        """
        :type n: int
        :rtype: int
        """
        left, right = 1, n
        while left < right:
            mid = left + (right-left)//2
            if isBadVersion(mid):
                right = mid
            else:
                left = mid + 1
        return left

if __name__ == '__main__':
    result = Solution().firstBadVersion(5)
    print(result)

540. 有序数组中的单一元素

题目描述

给定一个只包含整数的有序数组，每个元素都会出现两次，唯有一个数只会出现一次，找出这个数。

示例 1:

输入: [1,1,2,3,3,4,4,8,8]
输出: 2
示例 2:

输入: [3,3,7,7,10,11,11]
输出: 10
注意:

您的方案应该在 O(log n)时间复杂度和 O(1)空间复杂度中运行。

解题思路

如果题目不限制在 O(log n)时间复杂度运行，可使用异或运算。

def singleNonDuplicate(self, nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    if len(nums) == 0:
        return 0
    res = 0
    for i in nums:
        res ^= i
    return res

使用二分查找法实现O(log n)时间复杂度和 O(1)空间复杂度。
初始令左右指针分别为 0，len(nums)-1;
当left<= right时循环：
mid = left+(right-left)//2

当nums[mid] == nums[mid-1]时，数组可以分为[left, mid-2], [mid+1, right]两部分，目标元素位于长度为奇数的子数组中;

当mid为奇数时，说明[left, mid-2]长度为偶数，则目标位于[mid+1, right]，令left = mid +1;
当mid为偶数时，说明[left, mid-2]长度为奇数，则目标位于该数组内，令right = mid -1;
同理当nums[mid] == nums[mid+1]时，数组可以分为[left, mid-1], [mid+2, right]两部分，目标元素位于长度为奇数的子数组中;

当mid为奇数时，说明[left, mid-1]长度为奇数，则目标位于该数组内，令right = mid -1;
当mid为偶数时，说明[left, mid-1]长度为偶数，则目标位于[mid+2, right]，令left = mid +1;
当nums[mid]与nums[mid - 1], nums[mid + 1]均不相等，则返回nums[mid]。

class Solution(object):
    def singleNonDuplicate(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if len(nums) == 0:
            return 0
        left, right = 0, len(nums)-1
        while left <= right:
            mid = left + (right-left) //2
            if mid-1 >= 0 and nums[mid] == nums[mid-1]:
                if mid %2 == 1:
                    left = mid + 1
                else:
                    right = mid - 2
            elif mid+1 <= len(nums)-1 and nums[mid] == nums[mid+1]:
                if mid %2 == 1:
                    right = mid - 1
                else:
                    left = mid + 2
            else:
                return nums[mid]
if __name__ == '__main__':
    result = Solution().singleNonDuplicate([3,3,7,7,10,11,11])
    print(result)

744. 寻找比目标字母大的最小字母

题目描述

给定一个只包含小写字母的有序数组letters 和一个目标字母 target，寻找有序数组里面比目标字母大的最小字母。

数组里字母的顺序是循环的。举个例子，如果目标字母target = ‘z’ 并且有序数组为 letters = [‘a’, ‘b’]，则答案返回 ‘a’。

示例:

输入:
letters = [“c”, “f”, “j”]
target = “a”
输出: “c”

输入:
letters = [“c”, “f”, “j”]
target = “c”
输出: “f”
输入:
letters = [“c”, “f”, “j”]
target = “d”
输出: “f”

输入:
letters = [“c”, “f”, “j”]
target = “g”
输出: “j”

输入:
letters = [“c”, “f”, “j”]
target = “j”
输出: “c”

输入:
letters = [“c”, “f”, “j”]
target = “k”
输出: “c”
注:
1. letters长度范围在[2, 10000]区间内。
2. letters 仅由小写字母组成，最少包含两个不同的字母。
3. 目标字母target 是一个小写字母。

解题思路

二分搜索。
注意当有重复字母时，如[“e”,”e”,”e”,”e”,”e”,”e”,”n”,”n”,”n”,”n”],”e”，当letters[mid] 小于及等于 target时，left都要向前走一步;
如果left大于右边界时，说明target比数组里的所有字母都大，返回letters[0];
否则返回letters[left]。

class Solution(object):
    def nextGreatestLetter(self, letters, target):
        """
        :type letters: List[str]
        :type target: str
        :rtype: str
        """
        if len(letters) == 0:
            return ''
        left, right = 0, len(letters)-1
        while left <= right:
            mid = left + (right-left)//2
            if letters[mid] <= target:
                left = mid + 1
            else:
                right = mid - 1
        return  letters[0] if left == len(letters) else letters[left]
if __name__ == '__main__':
    result = Solution().nextGreatestLetter(["e","e","e","e","e","e","n","n","n","n"],"e")
    print(result)