时间戳

首页 > 技术文章 > Leetcode中几道二分查找(Binary Search)的算法题总结

Leetcode中几道二分查找(Binary Search)的算法题总结

kukri 2018-02-28 18:00 原文

二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。二分查找法的时间复杂度是对数级别的，O(log2n)

public int binarySearch(int [] array, double key) {
　　int l = 0;
　　int r = array.length - 1;
　　while (l <= r) {
　　　　int m = (l + r)/ 2;
　　　　if (key == array[m])
　　　　　　return m;
　　　　else if (key < array[m])
　　　　　　r = m - 1;
　　　　else
　　　　　　l = m + 1;
　　}
　　return l;
}

如果key在array中，返回的是key在array中的位置，如果不在array中，返回的是key应该插入的位置也就是第一个大于key的位置。这里和java.util.Arrays类返回值-(low + 1)不太一样，个人觉得我这种写法做某些算法题更方便。

1. Sqrt(x)

实现 int sqrt(int x) 函数。计算并返回 x 的平方根。x 保证是一个非负整数。

分析：

这道题有两种解法，二分法和拟牛顿法

二分法 

class Solution(object):
    def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        """
        l = 0
        r = x // 2 + 1
        while l <= r:
            m = (l + r) // 2
            if m ** 2 <= x and (m + 1) ** 2 > x:
                return m
            elif m ** 2 > x:
                r = m - 1
            else:
                l = m + 1

牛顿法

class Solution:
    def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        """
        r = x
        while r*r > x:
            r = (r + x//r) // 2
        return r

 

2.Search in Rotated Sorted Array I 、II

假设按照升序排序的数组在预先未知的某个关键点上旋转。

（即 0 1 2 4 5 6 7 将变成 4 5 6 7 0 1 2）。

给你一个目标值来搜索，如果数组中存在这个数则返回它的索引，否则返回 -1。

你可以假设数组中不存在重复。

分析：

这是二分查找的一道变形题，因为rotate的缘故，当我们切取一半的时候可能会出现误区，所以我们要做进一步的判断。具体来说，假设数组是A，每次左边缘为l，右边缘为r，还有中间位置是m。在每次迭代中，分三种情况：
（1）如果target==A[m]，那么m就是我们要的结果，直接返回；
（2）如果A[m]<A[r]，那么说明从m到r一定是有序的（没有受到rotate的影响），那么我们只需要判断target是不是在m到r之间，如果是则把左边缘移到m+1，否则就target在另一半，即把右边缘移到m-1。
（3）如果A[m]>=A[r]，那么说明从l到m一定是有序的，同样只需要判断target是否在这个范围内，相应的移动边缘即可。
class Solution(object):
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        l = 0
        r = len(nums) - 1
        while l <= r:
            m = (l + r) // 2
            if nums[m] == target:
                return m
            if nums[m] < nums[r]:
                if target > nums[m] and target <= nums[r]:
                    l = m + 1
                else:
                    r = m - 1
            else:
                if target < nums[m] and target >= nums[l]:
                    r = m - 1
                else:
                    l = m + 1
        return -1

　　follow up:

如果数组元素允许重复，怎么办？

这会影响到程序的时间复杂度吗？会有怎样的影响，为什么？

分析：

和Search in Rotated Sorted Array唯一的区别是这道题目中元素会有重复的情况出现。不过正是因为这个条件的出现，出现了比较复杂的case，甚至影响到了算法的时间复杂度。原来我们是依靠中间和边缘元素的大小关系，来判断哪一半是不受rotate影响，仍然有序的。而现在因为重复的出现，如果我们遇到中间和边缘相等的情况，我们就丢失了哪边有序的信息，因为哪边都有可能是有序的结果。假设原数组是{1,2,3,3,3,3,3}，那么旋转之后有可能是{3,3,3,3,3,1,2}，或者{3,1,2,3,3,3,3}，这样的我们判断左边缘和中心的时候都是3，如果我们要寻找1或者2，我们并不知道应该跳向哪一半。解决的办法只能是对边缘移动一步，直到边缘和中间不在相等或者相遇，这就导致了会有不能切去一半的可能。所以最坏情况（比如全部都是一个元素，或者只有一个元素不同于其他元素，而他就在最后一个）就会出现每次移动一步，总共是n步，算法的时间复杂度变成O(n)。代码如下：

class Solution:
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        if not nums:
            return False
        l = 0
        r = len(nums) - 1
        while l <= r:
            m = (l + r) // 2
            if nums[m] == target:
                return True
            if nums[m] < nums[r]:
                if target > nums[m] and target <= nums[r]:
                    l = m + 1
                else:
                    r = m - 1
            elif nums[m] > nums[r]:
                if target < nums[m] and target >= nums[l]:
                    r = m -1
                else:
                    l = m + 1
            else:
                r -= 1
        return False

 

3.Find Minimum in Rotated Sorted Array I 、II

假设一个按照升序排列的有序数组从某未知的位置旋转。

（比如 0 1 2 4 5 6 7 可能变成 4 5 6 7 0 1 2）。

找到其中最小的元素。

你可以假设数组中不存在重复的元素。

分析：

二分法O(log2n)：

如果num[m] < num[r]，说明pivot也就是最小的元素在m左边，极端情况有可能num[m]就是pivot，所以r = m 而不是 r= m -1，如果num[m] > num[r]，则pivot在m的右边，所以l = m + 1

class Solution(object):
    def findMin(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        l = 0
        r = len(nums) - 1
        while l < r:
            m = (l + r) // 2
            if nums[m] < nums[r]:
                r = m
            else:
                l = m + 1
        return nums[l]

　　线性扫描O(n):　　

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

　　follow up:

数组中存在重复元素，处理方法与上一道题Search in Rotated Sorted Array一样，对边缘移动一步，直到边缘和中间不在相等或者相遇，这就导致了会有不能切去一半的可能。所以最坏情况（比如全部都是一个元素，或者只有一个元素不同于其他元素，而他就在最后一个）就会出现每次移动一步，总共是n步，算法的时间复杂度变成O(n)

class Solution(object):
    def findMin(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        l = 0 
        r = len(nums) - 1
        while l < r:
            m = (l + r) // 2
            if nums[m] < nums[r]:
                r = m
            elif nums[m] > nums[r]:
                l = m + 1
            else:
                r -= 1
        return nums[l]

 

4.Find Peak Element

峰值元素是指其值大于左右相邻值的元素。

给定一个输入数组，其中 num[i] ≠ num[i+1]，找到峰值元素并返回其索引。

数组可能包含多个峰值，在这种情况下，返回到任何一个峰值所在位置都可以。

你可以想象得到  num[-1] = num[n] = -∞。

例如，在数组 [1, 2, 3, 1]中 3 是峰值元素您的函数应该返回索引号2。

你的解决方案应该是对数复杂度的。

分析：

这道题与Find Minimum in Rotated Sorted Array很像，依然可以用二分法或者线性扫描两种方法解决。

二分法O(log2n)：

如果nums[m] > nums[m+1]，则说明m的左侧肯定存在峰值，因为如果nums[m-1] < nums[m]，则说明m是峰值元素，如果说nums[m -1] > nums[m]，则m -1的左侧还存在峰值，如果一直到m = 0的话，那0这个位置的元素就是峰值。

class Solution(object):
    def findPeakElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        l = 0
        r = len(nums) - 1
        while l < r:
            m = (l + r) // 2
            if nums[m] < nums[m + 1]:
                l = m + 1
            else:
                r = m
        return l

线性扫描O(n):

如果当前元素m比前一元素m-1大的话，则继续向后搜索，如果小的话，说明前一元素m-1即为峰值，因为m-1之前的都比m-1小。

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

 

 

参考链接：

http://blog.csdn.net/linhuanmars/article/details/20588511　

推荐阅读