前提条件：有序
最常用的二分查找场景：寻找一个数、寻找左侧边界、寻找右侧边界。
二分查找框架

  1. def binary_search(alist, item):
  2.     left = 0
  3.     right = len(alist) - 1
  5.     while ...:
  6.         mid = left + (right - left) // 2
  7.         if alist[mid] == item:
  8.             return ...
  10.         elif item < alist[mid]:
  11.             right = ...
  13.         else:
  14.             left = ...
  15.     return ...

注意：计算 mid 时需要防止溢出，代码中 left + (right - left) / 2 和 (left + right) / 2 的结果相同，但是有效防止了 left 和 right 太大直接相加导致溢出。

二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。
二分查找 - 图1

寻找一个数

  1. class Solution(object):
  2.     def search(self, nums, target):
  3.         '''二分查找，递归'''
  4.         if not nums:
  5.             return -1
  6.         mid = len(nums)//2
  7.         if nums[mid] > target:
  8.             return self.search(nums[:mid], target)
  9.         elif nums[mid] < target:
  10.             return self.search(nums[mid+1:], target)
  11.         else:
  12.             return mid
  13.         return -1
  15. class Solution(object):
  16.     def search(self, nums, target):
  17.     '''二分查找，非递归'''
  18.         if not nums:
  19.             return -1
  20.         left = 0
  21.         right = len(nums) - 1
  22.         while left < right:
  23.             mid = (left + right)//2
  24.             if nums[mid] > target:
  25.                 right = mid - 1
  26.             elif nums[mid] < target:
  27.                 left = mid + 1
  28.             else:
  29.                 return mid
  30.         return -1

寻找重复数（这是个中等题）

给定一个包含 n + 1 个整数的数组 nums ，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。
假设 nums 只有 一个重复的整数 ，找出 这个重复的数 。
输入：nums = [1,3,4,2,2]
输出：2
输入：nums = [3,1,3,4,2]
输出：3

  1. class Solution(object):
  2.     def findDuplicate(self, nums):
  3.         # 方法一：我怎么也没想到，这竟然能和环形链表扯上关系
  4.         pre = nums[0]
  5.         cur = nums[nums[0]]
  6.         while pre != cur:
  7.             pre = nums[pre]
  8.             cur = nums[nums[cur]]
  9.         pre = 0
  10.         while pre != cur:
  11.             pre = nums[pre]
  12.             cur = nums[cur]
  13.         return cur
  16.         # 方法二：快慢指针
  17.         left = 1
  18.         right = len(nums) - 1
  20.         while left < right:
  21.             mid = (right + left ) // 2
  22.             # 计数， 找小于等于mid的个数
  23.             cnt = 0
  24.             for num in nums:
  25.                 if num <= mid:
  26.                     cnt += 1
  27.             # <= 说明 重复元素再右半边
  28.             if cnt <=  mid:
  29.                 left  = mid + 1
  30.             else:
  31.                 right = mid
  32.         return left
  35.         # 方法三：散列表解法
  36.         dicts = {}
  37.         for i in range(len(nums)):
  38.             if nums[i] in dicts:
  39.                 return nums[i]
  40.             else:
  41.                 dicts[nums[i]] = 1
  42.         return False

搜索旋转排序数组

给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的索引，否则返回 -1 。
输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4
输入：nums = [4,5,6,7,0,1,2], target = 3
输出：-1

  1. class Solution(object):
  2.     def search(self, nums, target):
  3.         if len(nums) == 0:
  4.             return -1
  6.         left = 0
  7.         right = len(nums) - 1
  9.         while left <= right:
  10.             mid = (left + right) // 2
  11.             if nums[mid] == target: # 如果中间值是目标，直接返回
  12.                 return mid
  13.             if nums[mid] >= nums[left]:
  14.                 if nums[mid] >= target >= nums[left]:
  15.                     right = mid - 1
  16.                 else:
  17.                     left = mid + 1
  18.             else:
  19.                 if nums[mid] <= target <= nums[right]:
  20.                     left = mid + 1 
  21.                 else:
  22.                     right = mid - 1
  23.         return -1

搜索旋转排序数组 II（数据可能有重复）

假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [0,0,1,2,2,5,6] 可能变为 [2,5,6,0,0,1,2] )。本题中的 nums 可能包含重复元素。
编写一个函数来判断给定的目标值是否存在于数组中。若存在返回 true，否则返回 false。
输入: nums = [2,5,6,0,0,1,2], target = 0
输出: true
输入: nums = [2,5,6,0,0,1,2], target = 3
输出: false

  1. class Solution(object):
  2.     def search(self, nums, target):
  3.         # 依旧是1的答案，通用
  4.         if len(nums) == 0:
  5.             return -1
  7.         left = 0
  8.         right = len(nums) - 1
  10.         while left <= right:
  11.             mid = (left + right) // 2
  12.             if nums[mid] == target: # 如果中间值是目标，直接返回
  13.                 return mid
  14.             if nums[mid] >= nums[left]:
  15.                 if nums[mid] >= target >= nums[left]:
  16.                     right = mid - 1
  17.                 else:
  18.                     left = mid + 1
  19.             else:
  20.                 if nums[mid] <= target <= nums[right]:
  21.                     left = mid + 1 
  22.                 else:
  23.                     right = mid - 1
  24.         return -1

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

给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。
输入：nums = [3,4,5,1,2]
输出：1
解释：原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。
输入：nums = [4,5,6,7,0,1,2]
输出：0
解释：原数组为 [0,1,2,4,5,6,7] ，旋转 4 次得到输入数组。

  1. class Solution(object):
  2.     def findMin(self, nums):
  3.         left = 0
  4.         right = len(nums)-1
  6.         while left < right:
  7.             mid = (left+right)//2
  8.             if nums[mid] < nums[right]:
  9.                 right = mid
  10.             else:
  11.                 left = mid + 1
  12.         return nums[left]

寻找旋转排序数组中的最小值 II（有重复项）

给你一个可能存在 重复 元素值的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。
输入：nums = [1,3,5]
输出：1
输入：nums = [2,2,2,0,1]
输出：0

  1. class Solution(object):
  2.     def findMin(self, nums):
  3.         left = 0
  4.         right = len(nums) - 1
  6.         while left < right:
  7.             mid = (left+right)//2
  8.             # 如果nums[mid] < nums[right]，说明最小值在左边，并且最小值有可能就是nums[mid]
  9.             if nums[mid] < nums[right]:
  10.                 right = mid
  11.             # 如果nums[mid] > nums[right]，说明最小值在右边
  12.             elif nums[mid] > nums[right]:
  13.                 left = mid + 1
  14.             # 相等则r索引递减即可例如处理[1,2,2,2]    
  15.             else:
  16.                 right = right - 1
  17.         # 返回最后lr指向的值即可
  18.         return nums[left]

两个数组的交集

给定两个数组，编写一个函数来计算它们的交集。
输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]
输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[9,4]

  1. class Solution(object):
  2.     def intersection(self, nums1, nums2):
  3.         dicts = {}
  4.         res = []
  5.         for i in range(len(nums1)):
  6.             if nums1[i] in dicts:
  7.                 dicts[nums1[i]] += 1
  8.             else:
  9.                 dicts[nums1[i]] = 1
  10.         for i in range(len(nums2)):
  11.             if nums2[i] in dicts:
  12.                 res.append(nums2[i])
  13.         return list(set(res))

两个数组的交集 II

给定两个数组，编写一个函数来计算它们的交集。
输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2,2]
输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[4,9]

  1. class Solution(object):
  2.     def intersect(self, nums1, nums2):
  3.         dicts = {}
  4.         res = []
  5.         for i in range(len(nums1)):
  6.             if nums1[i] in dicts:
  7.                 dicts[nums1[i]] += 1
  8.             else:
  9.                 dicts[nums1[i]] = 1
  10.         for i in range(len(nums2)):
  11.             if nums2[i] in dicts:
  12.                 # 就比I多了两行代码
  13.                 if dicts[nums2[i]] > 0:
  14.                     res.append(nums2[i])
  15.                     dicts[nums2[i]] -= 1
  16.         return res

寻找峰值

峰值元素是指其值大于左右相邻值的元素。
给你一个输入数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。
你可以假设 nums[-1] = nums[n] = -∞ 。
输入：nums = [1,2,3,1]
输出：2
解释：3 是峰值元素，你的函数应该返回其索引 2。
输入：nums = [1,2,1,3,5,6,4]
输出：1 或 5
解释：你的函数可以返回索引 1，其峰值元素为 2；
或者返回索引 5， 其峰值元素为 6。

  1. class Solution(object):
  2.     def findPeakElement(self, nums):
  3.         # 上坡必有峰
  4.         left = 0
  5.         right = len(nums)-1
  6.         while left < right:
  7.             mid = (left+right)//2
  8.             if nums[mid] < nums[mid+1]: 
  9.                 left = mid + 1
  10.             else: 
  11.                 right = mid
  12.         return left

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

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
进阶：
你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗？
输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]
输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]
输入：nums = [], target = 0
输出：[-1,-1]

  1. class Solution(object):
  2.     def searchRange(self, nums, target):
  3.         # 使用二分查找找到对应数字，然后在定义另外两个变量扩大窗口找范围
  4.         if target not in nums: 
  5.             return [-1, -1]
  7.         left = 0
  8.         right = len(nums)-1
  10.         while right >= left:
  11.             mid = (left + right) // 2
  12.             if nums[mid] > target:
  13.                 right = mid - 1
  14.             elif nums[mid] < target:
  15.                 left = mid + 1
  16.             else:
  17.                 l = r = mid
  18.                 # 这里需要考虑为0的情况，切记！！！！！！！！！！
  19.                 while l >= 0 and nums[l] == target:
  20.                     l -= 1
  21.                 while r < len(nums) and nums[r] == target:
  22.                     r += 1
  23.                 return [l+1, r-1]
  24.         return [-1, -1]

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

给你一个排序后的字符列表 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. class Solution(object):
  2.     def nextGreatestLetter(self, letters, target):
  3.         if letters[-1] <= target or letters[0] > target:
  4.             return letters[0]
  6.         left = 0
  7.         right = len(letters) - 1
  8.         while left < right:
  9.             mid = (left + right) // 2
  10.             if letters[mid] == target:
  11.                 # 等于目标值，往右找
  12.                 left = mid + 1
  13.             elif letters[mid] < target:
  14.                 # 比目标值小，往右找
  15.                 left = mid + 1
  16.             else:
  17.                 # 比目标值大，可能就是要找的数！
  18.                 right = mid
  19.         return letters[left]

找到 K 个最接近的元素*

给定一个排序好的数组 arr ，两个整数 k 和 x ，从数组中找到最靠近 x（两数之差最小）的 k 个数。返回的结果必须要是按升序排好的。
整数 a 比整数 b 更接近 x 需要满足：
|a - x| < |b - x| 或者
|a - x| == |b - x| 且 a < b
输入：arr = [1,2,3,4,5], k = 4, x = 3
输出：[1,2,3,4]
输入：arr = [1,2,3,4,5], k = 4, x = -1
输出：[1,2,3,4]

  1. class Solution(object):
  2.     def findClosestElements(self, arr, k, x):
  3.         # 直接定位mid为左边界；
  4.         # 查找mid+k的结果是否满足要求；
  5.         # 不满足的话二分法左右调整mid。
  7.         left = 0
  8.         #右 边界减k是因为mid为左边界，后面会使用mid+k进行判断
  9.         right = len(arr)-k 
  11.         while left < right:
  12.             mid = (right+left)//2
  13.             if x - arr[mid] > arr[mid + k] - x:
  14.                 left = mid + 1
  15.             else :
  16.                 right = mid
  17.         return arr[left : left + k]

x 的平方根

实现 int sqrt(int x) 函数。
计算并返回 x 的平方根，其中 x 是非负整数。
由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
输入: 4
输出: 2
输入: 8
输出: 2
说明: 8 的平方根是 2.82842…,
由于返回类型是整数，小数部分将被舍去。

  1. class Solution(object):
  2.     def mySqrt(self, x):
  3.         left = 0
  4.         right = x
  5.         res = -1
  6.         while left <= right:
  7.             mid = (left + right)//2
  8.             if mid * mid <= x:
  9.                 res = mid
  10.                 left = mid + 1
  11.             else:
  12.                 right = mid - 1
  13.         return res

有效的完全平方数

给定一个 正整数 num ，编写一个函数，如果 num 是一个完全平方数，则返回 true ，否则返回 false 。
进阶：不要 使用任何内置的库函数，如 sqrt 。
输入：num = 16
输出：true
输入：num = 14
输出：false

  1. class Solution(object):
  2.     def isPerfectSquare(self, num):
  3.         if num == 1:
  4.             return True
  5.         if num == 0:
  6.             return False
  7.         left = 1
  8.         right = num
  9.         while left < right:
  10.             mid = (left+right)//2
  11.             if mid*mid > num:
  12.                 right = mid
  13.             elif mid*mid < num:
  14.                 left = mid + 1
  15.             else:
  16.                 return True
  17.         return False