二分法--搜索旋转排序数组

哲子DZ

题意：假设有一个排序的按未知的旋转轴旋转的数组(比如，0 1 2 4 5 6 7 可能成为4 5 6 7 0 1 2)。给定一个目标值进行搜索，如果在数组中找到目标值返回数组中的索引位置，否则返回-1。假设数组中不存在重复的元素。例：给出[4, 5, 1, 2, 3]和target=1，返回 2；给出[4, 5, 1, 2, 3]和target=0，返回 -1。
答案代码如下：

1. class Solution(object):
   
2.     def search(self, nums, target):
   
3. 
   
4.         if not nums:
   
5.             return -1
   
6. 
   
7.         start, end = 0, len(nums) - 1
   
8.         while start + 1 < end:
   
9.             mid = start + (end - start) / 2
   
10.             if nums[mid] == target:
    
11.                 return mid
    
12.             elif nums[mid] > nums[start]:
    
13.                 if target >= nums[start] and target <= nums[mid]:
    
14.                     end = mid
    
15.                 else:
    
16.                     start = mid
    
17.             else:
    
18.                 if target >= nums[mid] and target <= nums[end]:
    
19.                     start = mid
    
20.                 else:
    
21.                     end = mid
    
22. 
    
23.         if nums[start] == target:
    
24.             return start
    
25.         if nums[end] == target:
    
26.             return end
    
27.         return -1

复制代码

两个问题：
问题1：根据题意用二分法，但是为什么条件是用mid和start比较，而不是一般二分法是mid和target比较？
问题2：if target >= nums[start] and target <= nums[mid]这个得else是什么？target <= nums[start] and target >= nums[mid]？两个条件还加了and，这个怎么想也想不明白。。
辛苦大家，麻烦帮忙解答我得问题，谢谢，谢谢！！
辛苦啦~~

ba21

第1： mid和start 是列表的下标。
第2：你上百度搜二分法，再深入了解下什么叫二分法。