此题来自：《剑指offer》面试题8
已经排序好的数组通常可以用二分法查找。
注意递归是可以将所有的邻接条件手动处理下，也才几个。
def circle_list_min(data,start,last):
if last < start:
return None
if start == last:
return data[start]
if start == last - 1:
return data[start] if data[start]<data[last] else data[last]
mid = (start + last)//2
if data[start] < data[mid]:
return circle_list_min(data,mid+1,last)
elif data[mid] < data[start]:
return circle_list_min(data,start,mid)
二分法递归代码1（last），同样是遵循了上面的原则，递归的时候宁愿多处理特殊情况，也不要凑通用代码：
# 二分法递归查找数字
def findNum(data,start,last,num):
if last < start:
return None
if start == last and data[start] != num:
return None
if start == last and data[start] == num:
return start
# 这种情况是考虑相隔1个的时候，下面的代码对于相隔1个这种临界情况要仔细思考才能
# 写好，不如就当作特殊情况处理
if start == last - 1:
if data[start] == num:
return start
elif data[last] == num:
return last
else:
return None
# 这段代码遵循的原则就是要缩小范围
mid = (start + last)//2
if num < data[mid]:
return findNum(data,start,mid-1,num)
elif data[mid] < num:
return findNum(data,mid+1,num)
else:
return mid
这次还是递归查找，但是用的是end不是last，两个数字的情况也非常容易处理了：
# 二分法查找数字
def findNum(data,start,end,num):
if end <= start:
return None
if start == end - 1:
if data[start] == num:
return start
else:
return None
# 这段代码遵循的原则就是要缩小范围
# 这里mid是第一段的end（注意区分last）
mid = (start + end)//2
if num < data[mid]:
return findNum(data,start,mid,num)
elif data[mid] < num:
return findNum(data,mid,end,num)
else:
return mid
写这段代码的时候遵循的原则：
1.end的表示
2.每一步都要缩小，不然就会发生死循环，关键要处理好临界状态
# 二分法迭代查找数字
# 用end，在有两个元素的时候mid=后者的序号，只有一个元素的时候mid就是那个元素的序号
def findNum(data,start,end,num):
while start < end:
mid = (start + end) // 2
if data[mid] == num:
return True
elif data[mid] < num:
start = mid+1
else:
end = mid
return False
同上可得，只不过end改为last，还是每次都要减少范围，特别是在临界状况下。
def findNum2(data,start,last,num):
while start <= last:
mid = (start + last) // 2
if data[mid] == num:
return mid + 1
elif data[mid] < num:
start = mid + 1
else:
last = mid - 1
return None
