沐瑶 / LearningNotes

forked from / LearningNotes
Create your Gitee Account
Explore and code with more than 6 million developers，Free private repositories ！：）

旋转数组的最小数字

暴力破解

class Solution:
def minNumberInRotateArray(self, rotateArray):
minNum = 0
# 第一种方法，就是遍历所以的元素，找出最小的
for i in range(0, len(rotateArray)):
minNum = minNum if minNum < rotateArray[i] and minNum != 0 else rotateArray[i]
return minNum

方式2

|a[middle] - left| < |a[middle] - right|

class Solution:

# 二分查找法
# 有序的数组中使用
def bSearch(self, array, target):
left = 0
right = len(array) - 1
while left < right:
# 右移1位，相当于除以2
mid = (left + right) >> 1
if target == mid:
return mid
if target > mid:
left = mid + 1
else:
right = mid - 1
return None

if __name__ == '__main__':
print(Solution().bSearch([1,2,3,4,5,6,7,8,9,10], 8))

# -*- coding:utf-8 -*-
class Solution:
# 二分查找法
# 有序的数组中使用
def minNumberInRotateArray(self, rotateArray):
if not rotateArray:
return None
left = 0
right = len(rotateArray) - 1
while left <= right:
middle = (left + right) >> 1
# middle 比两边的都小，说明是最小值
if rotateArray[middle] < rotateArray[middle - 1]:
return rotateArray[middle]
elif rotateArray[middle] < rotateArray[right]:
right = middle - 1
else:
left = middle + 1
return 0