算法题汇总 二分查找

Posted on |

二分查找

二分查找总结

二分搜索的注意：
编写二分查找的程序时
如果令 left <= right，则right = middle - 1;
如果令left < right，则 right = middle;

标准二分查找

循环条件包含left==right，循环的终止条件包含：

  • 找到目标值
  • left>right，这种情况发生于当left, mid, right指向同一个数时，这个数还不是目标值，则整个查找结束。
  • left + ((right -left) >> 1)，其实和 (left + right) / 2是等价的，这样写的目的一个是为了防止 (left + right)出现溢出，一个是用右移操作替代除法提升性能。
  • left + ((right -left) >> 1) 对于目标区域长度为奇数而言，是处于正中间的，对于长度为偶数而言，是中间偏左的。因此左右边界相遇时，只会是以下两种情况：
    • left/mid , right (left, mid 指向同一个数，right指向它的下一个数)
    • left/mid/right （left, mid, right 指向同一个数）
      即因为mid对于长度为偶数的区间总是偏左的，所以当区间长度小于等于2时，mid 总是和 left在同一侧。
1
2
3
4
5
循环条件： left <= right
中间位置计算： mid = left + ((right -left) >> 1)
左边界更新：left = mid + 1
右边界更新：right = mid - 1
返回值： mid / -1
1
2
3
4
5
6
7
8
9
10
11
12
class Solution(object):
    def search(self, nums):
        left,right=0,len(nums)-1
        while left<=right:
            mid=left+((right-left)>>1)
            if nums[mid]==target:
                return mid
            elif nums[mid]>target:
                right=mid-1
            else:
                left=mid+1
        return -1

35. 搜索插入位置

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

你可以假设数组中无重复元素。

思路1：标准二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution(object):
    def searchInsert(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        if not nums:
            return
        left,right=0,len(nums)-1
        while left<=right:

            mid=(left+right)/2
            print(left,mid,right)
            if nums[mid]==target:
                return mid
            elif nums[mid]<target:
                left=mid+1
            elif nums[mid]>target:
                right=mid-1
        return left
        # if nums[left]<target:
        #     return left+1
        # else:
        #     return left

思路2：二分查找左边界

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
    def searchInsert(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        if not nums:
            return 0

        left,right=0,len(nums)

        while left<right:
            mid=left+(right-left)/2
            if nums[mid] >=target:
                right=mid
            else:
                left=mid+1

        return left

思路3：bisect模块

1
2
3
4
5
6
7
8
class Solution(object):
    def searchInsert(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        return bisect.bisect_left(nums, target)

74. 搜索二维矩阵

编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：

每行中的整数从左到右按升序排列。
每行的第一个整数大于前一行的最后一个整数。

思路1：标准二分查找 & 二维矩阵

第一次二分搜索出在哪一行，第二次二分搜索直接确定存在
从左下角或右上角出发。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
"""从右上角出发"""
class Solution(object):
    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        if not matrix:
            return False

        i,j=0,len(matrix[0])-1
        while i<len(matrix) and j>=0:
            if matrix[i][j]==target:
                return True
            elif matrix[i][j]>target:
                j-=1
            else:
                i+=1

        return False

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
"""从左下角出发"""
class Solution(object):
    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        if not matrix or not len(matrix[0]):
            return False
        i,j=len(matrix)-1,0
        while i>=0 and j<len(matrix[0]):
            if matrix[i][j]==target:
                return True
            elif matrix[i][j]<target:
                j+=1
            else:
                i-=1
        return False

思路2：标准二分查找 & 一维数组

把矩阵从左到右、从上到下连起来就是一个递增的数组，可以用二分搜索来查找。现在只要找出数组下标到矩阵的映射关系就可以了：i -> [i // n][i % n]，其中i是数组中的下标，n是矩阵的宽。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        if not matrix or not len(matrix[0]):
            return False
        m,n=len(matrix),len(matrix[0])
        low,high=0,m*n-1
        while low<=high:
            mid=(low+high)//2
            if matrix[mid//n][mid%n]==target:
                return True
            elif matrix[mid//n][mid%n]<target:
                low=mid+1
            else:
                high=mid-1
        return False

69. x 的平方根

实现 int sqrt(int x) 函数。
计算并返回 x 的平方根，其中 x 是非负整数。
由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

思路1：math模块

1
2
3
4
5
6
7
class Solution(object):
    def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        """
        return int(math.sqrt(x))

思路2：标准二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution(object):
    def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        """
        if x<=1:
            return x

        left,right=1,x-1

        while left<=right:
            mid=left+((right-left)>>1)

            if mid>(x/mid):
                right=mid-1
            elif mid<(x/mid):
                if (mid+1)>(x/(mid+1)):
                    return mid
                left=mid+1
            else:
                return mid
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
    def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        """
        left,right=0,x
        while left<=right:
            mid=left+((right-left)>>1)
            if mid**2<=x<(mid+1)**2:
                return mid
            elif x<mid**2:
                right=mid-1
            else:
                left=mid+1

33. 搜索旋转排序数组

设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。
你可以假设数组中不存在重复的元素。
你的算法时间复杂度必须是 O(log n) 级别。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution(object):
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        #O(log(n))复杂度 二分法
        #关键在于定位到正确排序的一半。
        #如果 left。mid。right 一遍不符合右大于左。怎另一边正确排序
        if not nums:return -1
        left = 0
        right = len(nums)-1
        while left<=right:
            mid = (left+right)/2
            if nums[mid]==target:
                return mid
            # 左边是排序的
            if nums[left] <=nums[mid]:
                # target在左区间
                if nums[left]<=target<=nums[mid]:
                    right = mid-1
                else:
                    left = mid+1
            #右边是排序的
            else:
                if nums[mid]<=target<=nums[right]:
                    left = mid+1
                else:
                    right = mid-1
        return -1

81. 搜索旋转排序数组 II

假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [0,0,1,2,2,5,6] 可能变为 [2,5,6,0,0,1,2] )。
编写一个函数来判断给定的目标值是否存在于数组中。若存在返回 true，否则返回 false。
这是 搜索旋转排序数组 的延伸题目，本题中的 nums 可能包含重复元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution(object):
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: bool
        """
        left,right=0,len(nums)-1
        while left<=right:
            mid=(left+right)/2

            if nums[mid]==target:
                return True
            if nums[left]<nums[mid]:
                if nums[left]<=target<nums[mid]:
                    right=mid-1
                else:
                    left=mid+1
            elif nums[mid]<nums[right]:
                if nums[mid]<target<=nums[right]:
                    left=mid+1
                else:
                    right=mid-1
            elif nums[left]==nums[mid] or nums[mid]==nums[right]:
                if nums[mid]==nums[left]:
                    left+=1
                if nums[mid]==nums[right]:
                    right-=1
        return False

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution(object):
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: bool
        """
        left,right=0,len(nums)-1
        while left<=right:
            mid=(left+right)/2

            if nums[mid]==target:
                return True
            if nums[left]==nums[mid]==nums[right]:
                left+=1
                right-=1
            elif nums[left]<=nums[mid]:
                if nums[left]<=target<=nums[mid]:
                    right=mid-1
                else:
                    left=mid+1
            else:
                if nums[mid]<=target<=nums[right]:
                    left=mid+1
                else:
                    right=mid-1
        return False
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution(object):
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: bool
        """
        nums.sort()
        start = 0
        end = len(nums)-1
        while start<=end:
            mid = (start + end)/2
            if nums[end] < target < nums[start]:
                return False
            if target > nums[mid]:
                start = mid + 1
            elif target < nums[mid]:
                end = mid - 1
            else:
                return True
        return False

4. 寻找两个有序数组的中位数

给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。

请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。

你可以假设 nums1 和 nums2 不会同时为空。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution(object):
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        length=len(nums1)+len(nums2)
        if length&1==1:
            return self.findKth(nums1,nums2,length//2)
        else:
            return (self.findKth(nums1,nums2,length//2)+self.findKth(nums1,nums2,length//2-1))/2.

    def findKth(self, A, B, k):
        if not A:
            return B[k]
        if not B:
            return A[k]

        mid_a,mid_b=len(A)//2,len(B)//2
        median_a,median_b=A[mid_a],B[mid_b]

        if mid_a+mid_b<k:
            if median_a>median_b:
                return self.findKth(A, B[mid_b+1:],k-mid_b-1)
            else:
                return self.findKth(A[mid_a+1:],B,k-mid_a-1)
        else:
            if median_a>median_b:
                return self.findKth(A[:mid_a],B,k)
            else:
                return self.findKth(A,B[:mid_b],k)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        nums1.extend(nums2)
        res = nums1
        if not res:
            return None
        res.sort()
        len_res = len(res)
        if len_res % 2:
            return res[len_res//2] / 1.0
        else:
            return (res[len_res//2] + res[(len_res//2)-1]) / 2.0

二分查找左边界

利用二分法寻找左边界是二分查找的一个变体，应用它的题目常常有以下几种特性之一：

  • 数组有序，但包含重复元素
  • 数组部分有序，且不包含重复元素
  • 数组部分有序，且包含重复元素

左边界查找类型1：(数组有序&包含重复元素) or (部分有序&不包含重复元素）

循环条件：left>1)，等价于(left+right)/2
左边界更新：left=mid+1
有边界更新：right=mid
返回值：nums[left]==target?left:-1

最后left与right相邻，mid和left处于相同位置（mid处于中间偏左的位置），则下一步，无论怎样，left，mid，right都将处于相同位置，如果此时循环条件是left<=right，则需要再次进入循环，如果此时nums[mid]<target，循环正常终止；否则，会令right=mid，这样并没有改变left,mid,right的位置，将进入死循环。

所以，只需要遍历到left和right相邻就行，因为这一轮循环后，无论如何，left，mid，right都会指向相同位置，而且如果这个位置的值等于目标值，则它就一定是最左侧的目标值；如果不等于目标值，则说明没有找到目标值，这就是返回值

1
2
3
4
5
6
7
8
9
10
11
12
13
14

```Python
class Solution(object):
    def search(self, nums, target):
        left,right=0,len(nums)-1
        while left<right:
            mid=left+((right-left)>>1)
            if nums[mid]<target:
                left=mid+1
            else:
                right=mid
        if nums[left]==target:
            return left
        return -1

左边界查找类型2：数组部分有序且包含重复元素

这种条件下在我们向左收缩的时候，不能简单的令 right = mid，因为有重复元素的存在，这会导致我们有可能遗漏掉一部分区域，此时向左收缩只能采用比较保守的方式

它与类型1的唯一区别就在于对右侧值的收缩更加保守。这种收缩方式可以有效地防止我们一下子跳过了目标边界从而导致了搜索区域的遗漏。

  • 循环条件： left < right
  • 中间位置计算： mid = left + ((right -left) >> 1)
  • 左边界更新：left = mid + 1
  • 右边界更新：right = mid | right-=1
  • 返回值： nums[left] == target ? left : -1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
    def search(self, nums, target):
        left,right=0,len(nums)-1
        while left<right:
            mid=(left+right)/2
            if nums[mid]<target:
                left=mid+1
            elif nums[mid]>target:
                right=mid
            else:
                right-=1
        if nums[left]==target:
            return left
        return -1

278. 第一个错误的版本

假设你有 n 个版本 [1, 2, …, n]，你想找出导致之后所有版本出错的第一个错误的版本。

你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。

[left,right]表示搜索范围

  • 如果$isBadVersion(mid) \Rightarrow false$，下次迭代搜索范围应该是[mid+1,right],left=mid+1
  • 如果$isBadVersion(mid) \Rightarrow true$，不能保证mid是不是第一个错误版本，但可以确保mid之后的所有版本都是错误的，所以下次迭代搜索范围应该是[left,mid],right=mid

左边界查找类型1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# The isBadVersion API is already defined for you.
# @param version, an integer
# @return a bool
# def isBadVersion(version):

class Solution(object):
    def firstBadVersion(self, n):
        """
        :type n: int
        :rtype: int
        """
        left,right=1,n
        while left<right:
            mid=left+((right-left)>>1)
            if not isBadVersion(mid):
                left=mid+1
            else:
                right=mid
        return left

744. 寻找比目标字母大的最小字母

给定一个只包含小写字母的有序数组letters 和一个目标字母 target，寻找有序数组里面比目标字母大的最小字母。

数组里字母的顺序是循环的。举个例子，如果目标字母target = ‘z’ 并且有序数组为 letters = [‘a’, ‘b’]，则答案返回 ‘a’。

思路1：二分查找左边界

题目比较特殊，数组里字母的顺序是循环的且有序的（升序），搜索范围是[left,right]

  • letters[mid]<=target,[mid+1,right],left=mid+1
  • letters[mid]>target,[left,mid],right=mid

如果最后插入位置是letters.length，返回letters[0]

左边界查找类型1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
    def nextGreatestLetter(self, letters, target):
        """
        :type letters: List[str]
        :type target: str
        :rtype: str
        """
        left,right=0,len(letters)
        while left<right:
            mid=(left+right)/2
            if letters[mid]<=target:
                left=mid+1
            else:
                right=mid
        return letters[left%len(letters)]

思路2：二分查找 & bisect模块

1
2
3
4
5
6
7
8
9
class Solution(object):
    def nextGreatestLetter(self, letters, target):
        """
        :type letters: List[str]
        :type target: str
        :rtype: str
        """
        index=bisect.bisect(letters,target)
        return letters[index%len(letters)]

思路2：线性扫描

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

1
2
3
4
5
6
7
8
9
10
11
class Solution(object):
    def nextGreatestLetter(self, letters, target):
        """
        :type letters: List[str]
        :type target: str
        :rtype: str
        """
        for c in letters:
            if c>target:
                return c
        return letters[0]

1
2
3
4
5
6
7
8
9
10
11
12
class Solution(object):
    def nextGreatestLetter(self, letters, target):
        """
        :type letters: List[str]
        :type target: str
        :rtype: str
        """
        for i in range(len(letters)):
            if target < letters[i]:
                return letters[i]
            if target >= letters[-1]:
                return letters[0]

153. 寻找旋转排序数组中的最小值

假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。

请找出其中最小的元素。你可以假设数组中不存在重复元素。

这一题看上去没有重复元素，但是它也是查找左边界的一种形式，即可以看做是查找旋转到右侧的部分的左边界，有了这个思想，直接用二分查找左边界的模板就行了

左边界查找类型1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
    def findMin(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        left,right=0,len(nums)-1

        while left<right:
            mid=(left+right)/2
            if nums[mid]>nums[right]:
                left=mid+1
            else:
                right=mid
        return nums[left]

154. 寻找旋转排序数组中的最小值 II

假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。

请找出其中最小的元素。注意数组中可能存在重复的元素。

这道题目和上面153类似，只是多了一个条件——数组中可能包含重复元素，这就是我们之前说的二分查找左边界的第二种类型，在这种情况下，我们只能采用保守收缩的方式，以规避重复元素带来的对于单调性的破坏

左边界查找类型2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
    def findMin(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        left,right=0,len(nums)-1
        while left<right:
            mid=(left+right)/2

            if nums[mid]>nums[right]:
                left=mid+1
            elif nums[mid]<nums[right]:
                right=mid
            else:
                right-=1
        return nums[left]

1
2
3
4
5
6
7
class Solution(object):
    def findMin(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        return min(nums)

二分查找右边界

与二分查找左边界相比，中间位置计算遍历，在末尾加1，这样无论对于奇数或偶数，这个中间位置都是偏右的。

最后left和right相邻时，如果mid偏左，则left，mid指向同一个位置，right指向他们的下一个位置，在nums[left]已经等于目标值的情况下，这三个位置的值都不会更新，从而进入了死循环。所以让mid偏右，这样left就能向右移动。
判断条件和左右边界条件的更新方式三者之间必须配合使用
右边界的查找一般来说不会单独使用，如有需要，一般是需要同时查找左右边界。

循环条件： left < right
中间位置计算： mid = left + ((right -left) >> 1) + 1
左边界更新：left = mid
右边界更新：right = mid - 1
返回值： nums[right] == target ? right : -1

1
2
3
4
5
6
7
8
9
10
11
12
class Solution(object):
    def search(self, nums, target):
        left,right=0,len(nums)-1
        while left<right:
            mid=left+((right-left)>>1)+1
            if nums[mid]>target:
                right=mid-1
            else:
                left=mid
        if nums[right]==target:
            return right
        return -1

二分查找左右边界

34. 在排序数组中查找元素的第一个和最后一个位置

首先定位等于target的最左和最右元素的索引（并不仅仅是找到目标，返回true or false）。当找到一个匹配时，并不会终止，会继续查找直到left=right。

布尔值left，表示在target=nums[mid]时应该做什么。如果left=True，会在左边子数组递归，否者移动到右边。比如，当在i找到target，最左索引就不会出现在比i大的地方，就不用考虑右边子数组。这同样适用于最右索引。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution:
    # returns leftmost (or rightmost) index at which `target` should be inserted in sorted
    # array `nums` via binary search.
    def extreme_insertion_index(self, nums, target, left):
        lo = 0
        hi = len(nums)

        while lo < hi:
            mid = (lo + hi) // 2
            if nums[mid] > target or (left and target == nums[mid]):
                hi = mid
            else:
                lo = mid+1

        return lo


    def searchRange(self, nums, target):
        left_idx = self.extreme_insertion_index(nums, target, True)

        # assert that `left_idx` is within the array bounds and that `target`
        # is actually in `nums`.
        if left_idx == len(nums) or nums[left_idx] != target:
            return [-1, -1]

        return [left_idx, self.extreme_insertion_index(nums, target, False)-1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution(object):
    def searchRange(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        n = len(nums)
        if n < 1:
            return [-1,-1]

        left = 0
        right = n - 1
        # 找第一个位置
        while left <= right:
            mid = (left+right)//2
            if nums[mid] >= target:
                right = mid - 1
            else:
                left = mid + 1
        if left >= n or nums[left] != target:
            return [-1, -1]

        start = left

        # 找最后一个位置
        right = len(nums) - 1
        while left <= right:
            mid = (left+right)//2
            if nums[mid] > target:
                right = mid - 1
            else:
                left = mid + 1
        end = right

        return [start, end]

思路2：线性扫描

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def searchRange(self, nums, target):
        # find the index of the leftmost appearance of `target`. if it does not
        # appear, return [-1, -1] early.
        for i in range(len(nums)):
            if nums[i] == target:
                left_idx = i
                break
        else:
            return [-1, -1]

        # find the index of the rightmost appearance of `target` (by reverse
        # iteration). it is guaranteed to appear.
        for j in range(len(nums)-1, -1, -1):
            if nums[j] == target:
                right_idx = j
                break

        return [left_idx, right_idx]

1
2
3
4
5
6
7
8
9
10
11
12
class Solution(object):
    def searchRange(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        l = [loc for loc, val in enumerate(nums) if val == target]
        try:
            return [min(l), max(l)]
        except ValueError:
            return [-1, -1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
    def searchRange(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        start, end = -1, -1
        for index, num in enumerate(nums):
            if num == target and start == -1:
                start = index
                end = index
            if start >= 0 and num== target:
                end = index
        return [start, end]

二分查找极值

162. 寻找峰值

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

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

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

你可以假设 nums[-1] = nums[n] = -∞。

思路：递归二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
    def findPeakElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        return self.search(nums, 0, len(nums)-1)

    def search(self, nums, left, right):
        if left==right:
            return left
        mid=(left+right)/2
        if nums[mid]>nums[mid+1]:
            return self.search(nums, left, mid)
        return self.search(nums, mid+1, right)
  • 时间复杂度：O(lgn)，每一次递归，搜索空间减半，n是nums的长度
  • 空间复杂度：O(lgn)，每次递归，搜索空间减半，一共递归lg2次，因此递归树深lgn

思路2：迭代二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
    def findPeakElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        left,right=0,len(nums)-1
        while left<right:
            mid=(left+right)/2
            if nums[mid]>nums[mid+1]:
                right=mid
            else:
                left=mid+1
        return left
  • 时间复杂度：O(lgn)
  • 空间复杂度：O(1)

Python bisect

Python

Python 有一个 bisect 模块，用于维护有序列表。bisect 模块实现了一个算法用于插入元素到有序列表。在一些情况下，这比反复排序列表或构造一个大的列表再排序的效率更高。Bisect 是二分法的意思，这里使用二分法来排序，它会将一个元素插入到一个有序列表的合适位置，这使得不需要每次调用 sort 的方式维护有序列表。

bisect模块采用经典的二分算法查找元素。模块提供下面几个方法：

1
bisect.bisect_left(a, x, lo=0, hi=len(a))

定位x在序列a中的插入点，并保持原来的有序状态不变。参数lo和hi用于指定查找区间。如果x已经存在于a中，那么插入点在已存在元素的左边。函数的返回值是列表的整数下标。

1
bisect.bisect_right(a, x, lo=0, hi=len(a))

和上面的区别是插入点在右边。函数的返回值依然是一个列表下标整数。

1
bisect.bisect(a, x, lo=0, hi=len(a))

等同于

1
2

注意，前面这三个方法都是获取插入位置，也就是列表的某个下标的，并不实际插入。但下面三个方法实际插入元素，没有返回值。

bisect.insort_left(a, x, lo=0, hi=len(a))

1
2

将x插入有序序列a内，并保持有序状态。相当于```a.insert(bisect.bisect_left(a, x, lo, hi), x)```。碰到相同的元素则插入到元素的左边。这个操作通常是 O(log n) 的时间复杂度。

bisect.insort_right(a, x, lo=0, hi=len(a))

1
同上，只不过碰到相同的元素则插入到元素的右边。

bisect.insort(a, x, lo=0, hi=len(a))
等同于insort_right()```。