二分查找训练(python&&leetCode)

题目一：2020.08.29 [003] 魔术索引

1.题目描述

在数组A[0...n-1]中，有所谓的魔术索引，满足条件 A[i] = i 。给定一个有序整数数组，编写一种方法找出魔术索引，若有的话，在数组A中找出一个魔术索引，如果没有，则返回-1。若有多个魔术索引，返回索引值最小的一个。

示例1:
输入：nums = [0, 2, 3, 4, 5]
输出：0
说明: 0下标的元素为0

示例2:
输入：nums = [1, 1, 1]
输出：1

说明:
nums长度在[1, 1000000]之间
此题为原书中的 Follow-up，即数组中可能包含重复元素的版本

这道题出自于《程序员面试金典》 ，共有两个小问，第一小问为有序整数数组严格单调增，那么可以直接用二分法解决；第二小文与此题类似，整数数组单调不减，那么此题就不能继续用二分法做了。

2.解题思路

这道题有多种解法，最直接的就是遍历。

2.1 遍历查找

class Solution(object):
    def findMagicIndex(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        for i in range(len(nums)):
            if(nums[i] == i):
                return i
        
        return -1

时间复杂度：O(n)
空间复杂度：O(1)

2.2 在遍历的基础上做一个跳跃的优化

class Solution(object):
    def findMagicIndex(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        i = 0
        while i < len(nums):
            if(nums[i] == i):
                return i
            elif (i < nums[i]):
                i = nums[i]
            else:
                i += 1
        
        return -1

温馨提示：不可以使用 i ++ 哦
时间复杂度：O(n)
空间复杂度：O(1)

2.3 分治法

class Solution(object):
    def findMagicIndex(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        def getAnswer(nums, left, right):
            if(left > right):
                return -1
            mid = (left + right) // 2
            ans = getAnswer(nums, left, mid - 1)
            if(ans != -1):
                return ans
            elif(nums[mid] == mid):
                return mid
            else: 
                return getAnswer(nums, mid + 1, right)
        return getAnswer(nums, 0, len(nums) - 1)

时间复杂度：O(n)
空间复杂度：O(1)

二分查找训练(python&&leetCode)

原文：https://www.cnblogs.com/idella/p/13583025.html