二分查找法查找旋转数组的最小值（Python）

二分查找法与旋转数组最小值（Python）

题目描述

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。
输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。
例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。
NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。
例：非递减排序数组为1，2，3，4，5
输入的旋转数组为3，4，5，1，2

一、二分查找法

二分查找法适用于数据量较大，且提前排好序的数据，T(n)=O(log2n)

算法描述

	1   2   3   4   5   6   7   8   9   10   

若查找的数组元素target = 8:
1.设定left = 1，right = 10，middle = 5
middle的取值为（left+right)/2之后向下取整
2.若middle > target，则right = middle-1
若middle < target，则left = middle+1
3.逐次循环，循环边界为left <= right，若出现middle = target则查找成功，不然查找失败

示例代码

def bSearch(array,target):
    left= 0
    right= len(array)-1
    while left <= right :
        #除法没有移位的快
        # mid = (left + right)//2
        # 101 = 5 => 10 = 2
        #1100 = 12 => 110 = 6
        #一下用了 向右 移一位， 那么上面是解释，它就相当于 除以2 。
        mid = (left + right) >> 1
        #如果中间的数等于我们要找的数，那么就返回。
        if  array[mid] == target:
            return mid
        #如果说中间的数 < 目标的数，那么就说明，我们要找的数在右侧，所以左侧取值的索引需要改变为中间的索引+1；
        elif array[mid]< target:
            left = mid + 1
        #如果说中间的数 > 目标的数，那么就说明，我们要找的数在左侧，所以左侧取值的索引需要改变为中间的索引-1； 因为越往左索引值越小
        else:
            right = mid-1

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

二、旋转数组的最小数字

算法描述

1.通过观察可知输入数组中的最小数值为1，任意一个输入的旋转数组的最小值都有一个特点，即比前一个数小且比后个数大
2.在利用二分查找法查找时，若right < middle，则意味着右侧数据违背了元素递增的规律，即最小值一定在middle往后的数据中，即left = middle+1
3.若right > middle，则意味着middle之后的数据是递增规律，则最小值一定在middle的前面，即right = middle-1

示例代码

class Solution:
    def minNumberInRotateArray(self, rotateArray):
        #最小值 一定比前面的要小
        # 二分法查找数据  找左右的方法是：
        #右边的值大于中值，就说明最小值在左边
        if not rotateArray:
            return 0
        left = 0
        right = len(rotateArray) - 1
        while left <= right:
            mid = (left + right) >> 1
            #如果说中间的数的上一个数 > 中间数，那么就说明，我们要找的数就是这个中间的数，返回这个数。
            if rotateArray[mid - 1] > rotateArray[mid]:
                return rotateArray[mid]
            #如果说中间的数 < 中间数的上一个数，那么就说明，我们要找的数在二分法的左侧，所以右侧取值的索引需要改变为中间的索引-1；因为越往左索引值越小
            elif rotateArray[mid] < rotateArray[right]:
                right = mid - 1
            #否则就说明，我们要找的数在二分法的右侧，所以左侧取值的索引需要改变为中间的索引+1；因为越往右索引值越小
            else:
                left = mid + 1
        return 0
        #代码缺少输入输出

用右移1位比除以2更高效