# 折半查找
def half_find(arr, target):
frm = 0
to = len(arr) - 1
if to <= frm:
return frm
while frm <= to:
half = (frm + to) / 2 # frm <= half <= to
if arr[half] < target:
frm = half+1
elif arr[half] > target:
to = half-1
else:
return half
return -1
# 翻转数组
def revers(arr, s, t):
while s < t:
tmp = arr[s]
arr[s] = arr[t]
arr[t] = tmp
s += 1
t -= 1
# 左移和右移等价，左移n位，即又移N-n位
def recycleShiftLeft(arr, n):
n = n % len(arr)
revers(arr, 0, n-1)
revers(arr, n, len(arr)-1)
revers(arr, 0, len(arr)-1)
# 循环移位之后，分成了前后两部分，前半段所有值大于后半段任何值
def rotatemin(arr):
s = 0
t = len(arr)-1
m = 0
while s < t:
m = (s + t)/2
if arr[m] > arr[t]: # m和t不在同一段,故最小值在m+1 -- t中间
s = m+1
elif arr[m] < arr[t]: # m和t在同一段,故最小值在s-m中间
t = m # arr[m]可能是最小值哦，故不能t = m-1
return s
def rotatemax(arr):
if arr[0] < arr[-1]: # 此种情况没有循环移位，是正常的递增顺序
return len(arr)-1 #最后一位
else: # 有循环，则最小值前一位必是最大值
return rotatemin(arr)-1
if __name__ == "__main__":
arr = [1, -2, 3, 10, -4, 7, 2, -5]
InsertSort(arr)
print arr
recycleShiftLeft(arr, 1)
print arr
print rotatemin(arr)
print rotatemax(arr)
【数组】--旋转(循环)数组最小值，附:旋转数组和二分查找
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
推荐阅读更多精彩内容
- 本系列导航：剑指offer（第二版）java实现导航帖 面试题11：旋转数组的最小数字 题目要求：把一个数组最开始...
