【力扣Leetcode】二分查找专题（Python刷题）704，35，69，367，441，33，34，153，162，4

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        n=len(nums)
        if n==0:
            return -1
        left,right=0,n-1
        while left<=right:
            mid=(left+right)//2
            if nums[mid]>target:
                right=mid-1
            elif nums[mid]<target:
                left=mid+1
            else:
                return mid
        return -1

35. 搜索插入位置（简单）

题目要求

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

请必须使用时间复杂度为 O(log n) 的算法。

来源：力扣（LeetCode）

链接：

力扣

题解

方法一：

思路：因为left和right已经发生的交叉，left>right，所以返回的应该是left。

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        n = len(nums)
        left, right = 0, n-1
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] < target:
                left = mid + 1
            elif nums[mid] > target:
                right = mid -1
            else:
                return mid
        return left

Java

class Solution {
    public int searchInsert(int[] nums, int target) {
        int left = 0;
        int right = nums.length -1;
        int mid = 0;
        while (left<=right){
            mid=(left+right)/2;
            if (nums[mid]<target){
                left=mid+1;
            }
            else if(nums[mid]>target){
                right=mid-1;
            }
            else{
                return mid;
            }
        }
        return left;
    }
}

方法二：

思路：Python可以直接用bisect模块。

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        return bisect.bisect_left(nums,target)

69. x的平方根（简单）

题目要求

给你一个非负整数
x
，计算并返回
x
的

算术平方根

。

由于返回类型是整数，结果只保留

整数部分

，小数部分将被

舍去。

来源：力扣（LeetCode）

链接：

力扣

题解

方法一

：暴力解决，从头开始算，直到找到

1.某个数的平方恰好=x，输出该数；2.某个数的平方<x，但（该数+1）的平方>x，输出该数。

但是，该方法时间超限。

class Solution:
    def mySqrt(self, x: int) -> int:
        if x==0 or x==1:
            return x
        else:
            for cur in range(x):
                if cur**2<x and (cur+1)**2>x:
                    return cur
                elif cur**2==x:
                    return cur

方法二

：直接用库函数。

import math
class Solution:
    def mySqrt(self, x: int) -> int:
        return int(math.sqrt(x))

方法三

：牛顿法

牛顿法原理

：若想求2的平方根，列公式f(x)=x^2-2。当f(x)=0时，x=根号2。

在f(x)上随便取一点，以(2,2)为例，在该点做f(x)的切线，列出切线方程y=4x-6，求该切线方程在y=0时候的x值,

x=1.5

，将所求x值带回f(x)=0.25，此时这点坐标为(切线方程和x轴交点，对应的f(x)值)=(1.5,0.25)。

此时对这个点做上述操作：求切线方程y=4x-5.75，切向方程与x轴交点

x=1.4375

。

可以发现切线方程与x轴的交点从x=1.5到x=1.4375，如果继续迭代，x会不断逼近根号二的真值1.4142……，如果最开始的初始值选择别的值，也不会耽误计算，影响的只是迭代次数。

参考链接（里面有图）：

如何手工开根号？（简述Newton-Raphson 法） – 知乎

数学部分讲完了，接下来是总结规律：

class Solution:
    def mySqrt(self, x: int) -> int:
        t=x
        while t*t>x:
            t=(t+x/t)//2
        return int(t)

方法四

：二分法

class Solution:
    def mySqrt(self, x: int) -> int:
        left,right=0,x+1
        while left<=right:
            mid=(left+right)//2
            if mid**2>x:
                right=mid-1
            elif mid**2<x:
                left=mid+1
            else:
                return mid
        return left-1

牛顿法思路来源负雪明烛，参考链接：

【LeetCode】69. Sqrt(x) 解题报告（Python & C++）_负雪明烛的博客-CSDN博客

367.有效的完全平方数（简单）

题目要求

给定一个正整数 num ，编写一个函数，如果 num 是一个完全平方数，则返回 true ，否则返回 false 。

进阶：不要使用任何内置的库函数，如 sqrt 。

来源：力扣（LeetCode）

链接：

力扣

题解

方法一

：二分法

class Solution:
    def isPerfectSquare(self, num: int) -> bool:
        left,right=0,num+1
        while left<=right:
            mid=(left+right)//2
            if mid**2>num:
                right=mid-1
            elif mid**2<num:
                left=mid+1
            else:
                return True
        return False

方法二

：利用完全平方数的性质（是从1开始若干连续奇数的和）

class Solution:
    def isPerfectSquare(self, num: int) -> bool:
        i=1
        while num>0:
            num-=i
            i+=2
        return num==0

方法三

：牛顿法

class Solution:
    def isPerfectSquare(self, num: int) -> bool:
        t=num
        while t**2>num:
            t=(t+num/t)//2
        return t**2==num

方法二（利用完全平方性质）、方法三（牛顿法）思路来源负雪明烛

参考链接：

【LeetCode】367. Valid Perfect Square 解题报告（Java & Python）_负雪明烛的博客-CSDN博客

441.排列硬币（简单）

题目要求

你总共有 n 枚硬币，并计划将它们按阶梯状排列。对于一个由 k 行组成的阶梯，其第 i 行必须正好有 i 枚硬币。阶梯的最后一行可能是不完整的。

给你一个数字 n ，计算并返回可形成完整阶梯行的总行数。

来源：力扣（LeetCode）

链接：

力扣

题解

方法一：暴力尝试，判断是否正好排布，如果正好就返回行数；如果不正好就返回行数-1。

class Solution:
    def arrangeCoins(self, n: int) -> int:
        row=0
        while n>0:
            row+=1
            n-=row
        if n==0:
            return row
        else:
            return row-1

方法二：等差数列前n项和+二分法

#等差数列求和公式
sn=a1*n+n*(n-1)*d/2   # a1:第一项； d:公差
sn=(a1+an)*n/2        # an:第n项

class Solution:
    def arrangeCoins(self, n: int) -> int:
        left,right=0,n+1
        while left<=right:
            mid=(left+right)//2  
            sn=mid+mid*(mid-1)/2  # 等差数列求和公式，第一项a1=1，d=1，所以省略了
                                  # 两个求和公式，用哪个都行
            if sn>n:
                right=mid-1
            elif sn<n:
                left=mid+1
            else:
                return mid
        return left-1

方法三：等差数列前n项和，反向求解行数，并向下取整

sn=(a1+an)*n/2
2*sn=(1+n)*n
n**2+n+1/4=2*sn+1/4        # 中学数学，构成完全平方项
(n+1)**2=2*sn+1/4
n=math.sqrt(2*sn+1/4)-1/2  # 此处的sn是题目要求的目标值n

import math
class Solution:
    def arrangeCoins(self, n: int) -> int:
        return int(math.sqrt(2*n+1/4)-1/2)

33. 搜索旋转排序数组（中等）

题目要求

整数数组 nums 按升序排列，数组中的值互不相同。

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了旋转，使数组变为 [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]]（下标从 0 开始计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。

给你旋转后的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。

来源：力扣（LeetCode）

链接：

力扣

题解

二分法：根据二分法以mid为分界，划分数组左右两侧，使得各自有序，然后在用二分法在target满足的区间内进行寻找。

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left,right=0,len(nums)-1
        while left<=right:
            mid=(left+right)//2
            if nums[mid]==target:
                return mid
            if nums[mid]>nums[right]:     # 左侧有序
                if nums[mid]>target and nums[left]<=target:   # target在有序的左侧，则开始缩小区间搜索
                    right=mid-1
                else:          # target不在有序一侧，则重新划定有序区间
                    left=mid+1
            else:   #nums[mid]<nums[right]: 右侧有序
                if nums[mid]<target and nums[right]>=target:  # target在有序的右侧，则开始缩小区间搜索
                    left=mid+1
                else:          # target不在有序一侧，则重新划定有序区间
                    right=mid-1
        return -1

二分法思路来源：负雪明烛。链接：

【LeetCode】33. Search in Rotated Sorted Array 解题报告（Python & C++）_负雪明烛的博客-CSDN博客

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

题目要求

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

来源：力扣（LeetCode）

链接：

力扣

题解

二分法一

：利用二分法找target，找到后确认与target相同的左右边界。

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        left,right=0,len(nums)-1
        while left<=right:
            mid=(left+right)//2
            if nums[mid]>target:  
                right=mid-1
            elif nums[mid]<target:
                left=mid+1
            else:                    # 当利用二分法找到target后，确认左右边界。
                left,right=mid,mid   # 以mid为中心向左右移动
                # 指针左移直到找到与target不同的值（注意左边界不能超过0）
                while left>-1 and nums[left]==nums[mid]: 
                    left-=1
                # 指针右移直到找到与target不同的值（注意右边界不能超过nums的长度）
                while right<len(nums) and nums[right]==nums[mid]: 
                    right+=1
                return left+1,right-1 
        return -1,-1

二分法二

：用python内置函数

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        left=bisect.bisect_left(nums,target)   # left=第一个与target相同的元素下标
        right=bisect.bisect_right(nums,target) # right=最后一个与target相同的元素下标+1
        print("left= ",left,"right= ",right)
        if left==right: #没找到target时，left=right=0
            return -1,-1
        return left,right-1

二分法三

：定义两个函数，实现bisect_left，bisect_right。

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        left=self.lowwer_bound(nums,target)
        right=self.higher_bound(nums,target)
        if left==right:
            return -1,-1
        return left,right-1
    
    # target存在时，返回第一个与target相同元素的下标；target不存在时，返回target插入位置。
    def lowwer_bound(self,nums,target): 
        left,right=0,len(nums)-1
        while left<=right:
            mid=(left+right)//2
            if nums[mid]<target:  # 左右边界两个函数只在这个位置有区别
                left=mid+1
            else:
                right=mid-1
        return left
    
    # target存在时，返回右侧第一个与target不同元素下标；target不存在时，返回target插入位置。
    def higher_bound(self,nums,target):
        left,right=0,len(nums)-1
        while left<=right:
            mid=(left+right)//2
            if nums[mid]<=target: # 找到比target大的第一个数作为left
                left=mid+1
            else:
                right=mid-1
        return left               # 此处返回是left作为右边界

二分法二，三参考负雪明烛，链接：

【LeetCode】34. Find First and Last Position of Element in Sorted Array 解题报告（Python & C++）_负雪明烛的博客-CSDN博客

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

题目要求

已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次旋转后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：

若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]

若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]

注意，数组 [a[0], a[1], a[2], …, a[n-1]] 旋转一次的结果为数组 [a[n-1], a[0], a[1], a[2], …, a[n-2]] 。

给你一个元素值互不相同的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的最小元素。

来源：力扣（LeetCode）

链接：

力扣

题解

二分法一：

class Solution:
    def findMin(self, nums: List[int]) -> int:
        n=len(nums)
        left,right=0,n-1
        while left<=right:
            mid=(left+right)//2
            if nums[mid]>nums[right]:
                left=mid+1
            elif nums[left]<=nums[mid]<=nums[right]: # left，mid，right是按照顺序排列的时候，返回left
                return nums[left]
            else:       # nums[mid]<left:
                right=mid

二分法二：

思路类似负雪明烛方法三，传送门在下方。

class Solution:
    def findMin(self, nums: List[int]) -> int:
        n=len(nums)
        if n==1:
            return nums[0]
        left,right=0,n-1
        while nums[left]>nums[right]: # 当子序列也是经过旋转的时候，不断寻找有序的部分
            if right==left+1:         # 当左边界与有边界相邻的时候，返回右边界
                return nums[right]
            mid=(left+right)//2
            if nums[mid]>nums[right]:
                left=mid+1
            else:  # nums[mid]<nums[left]
                right=mid
        return nums[left]

二分法三：参考负雪明烛，传送门在下方。

参考链接：

【LeetCode】153. Find Minimum in Rotated Sorted Array 解题报告（Python）_负雪明烛的博客-CSDN博客

162.寻找峰值（中等）

题目要求

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

给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回任何一个峰值所在位置即可。

来源：力扣（LeetCode）

链接：

力扣

题解

二分法

：参考负雪明烛

class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        n=len(nums)
        if n==1:
            return 0
        left,right=0,n-1
        while left<right:
            mid=(left+right)//2
            if nums[mid]<nums[mid+1]: # 找升序数组，逐渐逼近坡顶
                left=mid+1
            else:                     # nums[mid]>=nums[mid+1]的时候即为坡顶
                right=mid
        return left

参考链接：

【LeetCode】162. Find Peak Element 解题报告（Python）_负雪明烛的博客-CSDN博客

4. 寻找两个正序（困难）

题目要求

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的中位数。

算法的时间复杂度应该为 O(log (m+n)) 。

来源：力扣（LeetCode）

链接：

力扣

题解

：

第一遍理解错了，搞了个求中值（代码就不放了），第二遍搞成了每个列表的中值再求平均（代码先放这里吧），但是题目是让我们合并数组的中值。干饭去了，明天接着弄。

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:  
        nums1=self.median_array(nums1)
        nums2=self.median_array(nums2)
        nums1.extend(nums2)
        nums1.sort()
        n=len(nums1)
        if n==0:
            return 0
        elif n==1:
            return nums1[0]
        elif n==3:
            return nums1[1]
        else:
            return (nums1[n//2]+nums1[n//2-1])/2

    def median_array(self,num):
        n=len(num)
        if n==0:
            return []
        if n==1:
            return [num[0]]
        mid=n//2
        print(mid)
        if n%2==0:
            return [num[mid-1],num[mid]]
        else:
            return [num[mid]]

重新来过

方法一

：两个数组合并，掉包排序，根据合并后的数组长度求中位数。

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        nums1.extend(nums2)     # 合并数组
        nums1.sort()            # 排序
        n=len(nums1) 
        if n%2==0:              # 数组长度为偶数个，则返回中间两个数的平均值
            return (nums1[n//2]+nums1[n//2-1])/2
        else:                   # 数组长度为奇数个，则返回中间那个数
            return nums1[n//2]

方法二

：思路参考第88题，边排序边合并数组。然后再根据有序数组求中位数

第88题传送门：

力扣


【刷题笔记（一起刷题）】Leetcode 面试最常考100题（负雪明烛整理题集）_Paige_sci的博客-CSDN博客

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        m=len(nums1)
        n=len(nums2)
        nums=nums1
        nums.extend(nums2)
        while m>0 and n>0:
            if nums1[m-1]>nums2[n-1]:
                nums[m+n-1]=nums1[m-1]
                m-=1
            else:
                nums[m+n-1]=nums2[n-1]
                n-=1
        nums[:n]=nums2[:n]
        print(nums)
        l=len(nums)
        if l%2==0:
            return (nums[l//2]+nums[l//2-1])/2
        else:
            return nums[l//2]

方法三：二分法

，参考链接在下方，照着扒了个python的，但是我也没太看明白。/捂脸

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        m=len(nums1)
        n=len(nums2)
        left,right=(m+n+1)//2,(m+n+2)//2
        return (self.getkth(nums1,0,m-1,nums2,0,n-1,left)+self.getkth(nums1,0,m-1,nums2,0,n-1,right))/2

    def getkth(self,nums1,start1,end1,nums2,start2,end2,k):
        len1=end1-start1+1
        len2=end2-start2+1
        # 保证nums1是更短一点的数组
        if len1>len2:
            return self.getkth(nums2,start2,end2,nums1,start1,end1,k)
        if len1==0:
            return nums2[start2+k-1]
        if k==1:
            return min(nums1[start1],nums2[start2])
        i=start1+min(len1,k//2)-1
        j=start2+min(len2,k//2)-1
        if nums1[i]>nums2[j]:
            return self.getkth(nums1,start1,end1,nums2,j+1,end2,k-(j-start2+1))
        else:
            return self.getkth(nums1,i+1,end1,nums2,start2,end2,k-(i-start1+1))

参考链接：

Leetcode4.寻找两个有序数组的中位数——巧妙使用二分法_No_Game_No_Life_的博客-CSDN博客_寻找两个有序数组的中位数

原文链接：https://blog.csdn.net/m0_52023710/article/details/124522703

704.二分查找（简单）

35. 搜索插入位置（简单）

69. x的平方根（简单）

367.有效的完全平方数（简单）

441.排列硬币（简单）

33. 搜索旋转排序数组（中等）

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

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

162.寻找峰值（中等）

4. 寻找两个正序（困难）

你可能也喜欢