二分搜索怎么理解

我最开始对于二分搜索的印象就是CS50里面professor撕书的场面。 CS50的professor 要找一个电话号码， 他每次都可以根据条件撕掉书剩下的一半。 最后书只剩下一页， 他也找到了自己想要的号码。
这个就是binary search的真谛。 根据条件排除另外一半， 留下我们想要的一半。最后剩下的， 就是我们想要的。

以下是binary search的code.

1. def binary_search(self, nums, target):
   
2.   start, end = 0, len(nums)-1
   
3.   while (start + 1 < end):
   
4.     mid = start + (end - start) // 2    if nums[mid] == target:
   
5.       return mid
   
6.     # 当我们知道target比middle value来得大， 而且整个array是sorted, 我们可以知道答案只在右边那一半， 所以我们舍弃左边。 把start pointer移到右边那一半的开始。
   
7.     elif nums[mid] < target:
   
8.       start = mid
   
9.     # 同理， 当我们知道target比middle value小， 我们舍弃右边那一把。 把end pointer 移到左边那一半的结尾。
   
10.     else:
    
11.       end = mid
    
12.   if nums[end] == target:
    
13.     return end
    
14.   if nums[start] == target:
    
15.     return start
    
16.   return -1

复制代码

leetcode 34 https://leetcode.com/problems/fi ... nt-in-sorted-array/

1. class Solution(object):
   
2.     def searchRange(self, nums, target):
   
3.         """
   
4.         :type nums: List[int]
   
5.         :type target: int
   
6.         :rtype: List[int]
   
7.         """
   
8.         if nums is None or len(nums) == 0:
   
9.           return [-1, -1]
   
10.         return [self.find_first(nums, target), self.find_last(nums, target)]
    
11.     def find_last(self, nums, target):
    
12.       """
    
13.       :rtype: int
    
14.       """
    
15.       start, end = 0, len(nums)-1
    
16.       while (start + 1 < end):
    
17.         mid = start + (end - start) // 2
    
18.         # 当我们得知target和middle value相等， 我们可以确定右边那一半是我们想要的， 我们舍弃左边那一半。
    
19.         # 右边那一半肯定放着 the last index of target。
    
20.         # 这么说的原因是因为 右边那一半已经至少有一个与target相等的值， 现在只有两种情况， 一个是右边那一半只有一个与target相等的值， 那么我们也已经包括把最终答案包括在右边。
    
21.         # 另外一种情况是右边那一半有多个与target相等的值， 那种情况我们也是已经把最终答案包括在右边 （因为这个题目要求的是last index of the element）。
    
22.         # 同理可以推导出find_first_index
    
23.         if nums[mid] == target:
    
24.           start = mid
    
25.         elif nums[mid] < target:
    
26.           start = mid
    
27.         else:
    
28.           end = mid
    
29.       
    
30.       if nums[end] == target:
    
31.         return end
    
32.       if nums[start] == target:
    
33.         return start
    
34.       return -1
    
35.    
    
36.     def find_first(self, nums, target):
    
37.       """
    
38.       : rtypes: int
    
39.       """
    
40.       start, end = 0, len(nums) - 1
    
41.       while start + 1 < end:
    
42.         mid = start + (end - start) // 2
    
43.         if nums[mid] == target:
    
44.           end = mid
    
45.         elif nums[mid] > target:
    
46.           end = mid
    
47.         else:
    
48.           start = mid
    
49.       if nums[start] == target:
    
50.         return start
    
51.       if nums[end] == target:
    
52.         return end
    
53.       return -1

复制代码

同样的道理可以放在 search in rotated sorted array - https://leetcode.com/problems/search-in-rotated-sorted-array/
这道题目 我们主要要知道怎么提取出条件， 这个条件就是用来舍弃另外一半的条件。
我们通常知道sorted in order是一个很重要的提示， 这个是在提示我们可以用binary search, 因为sorted可以作为舍弃另外一半的条件。
这个题目的条件是rotated sorted array， 他也有sorted的部分。 我们可以做的就是只在sorted的地方用binary search

1. class Solution(object):
   
2.     def search(self, nums, target):
   
3.         """
   
4.         :type nums: List[int]
   
5.         :type target: int
   
6.         :rtype: int
   
7.         """
   
8.         if not nums or not len(nums):
   
9.           return -1
   
10.         
    
11.         start, end = 0, len(nums)-1
    
12.         while start+1 < end:
    
13.           mid = (start+end)//2
    
14.           if nums[mid] == target:
    
15.             return mid          # 一共会有两种rotated的情况， 一个是前面那一半是sorted， 一个是后面那一半才是sorted
    
16.           # e.g [1, 2, 3, 4, 5, 6] => [2, 3, 4, 5, 6, 1] or [5, 6, 1, 2, 3, 4] 这两个都是rotated sorted, 不过一个是前面那一半那个是perfectly sorted, 一个是后面那一半perfectly sorted
    
17.           if nums[mid] <= nums[end]: # mid to end is in ascending order
    
18.             # 现在我们可以确认这一半是perfectly sorted
    
19.             # 我们现在判断target是否在这一半里面， 如果不是， 我们就舍弃这一半
    
20.             if nums[mid]<= target <= nums[end]:
    
21.               start = mid
    
22.             else:
    
23.               end = mid
    
24.           else: # start to mid is in ascending order
    
25.             if nums[start] <= target <= nums[mid]:
    
26.               end = mid
    
27.             else:
    
28.               start = mid
    
29.         if nums[start] == target:
    
30.           return start
    
31.         if nums[end] == target:
    
32.           return end
    
33.         return -1

复制代码

最后总结一下binary search, binary search真谛就是舍弃另外一半， 然后取我们要的那一半， 再在最后剩下的东西里面挑我们要的。
在所有binary search题目里面，我们要发现可以用来舍弃另外一半的条件。

最后求米

一个数组, 全是0 -> [0,0,0, ... 0]

用二分分别找第一个0, 和最后一个0的位置.

代码写明白了你就会做了.