【力扣】Python分类刷题（二分查找专题）704，35，69，367，441

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

请必须使用时间复杂度为 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){
                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)

给你一个非负整数 x ，计算并返回 x 的 算术平方根 。

由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。

来源：力扣（LeetCode）

链接：力扣

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

1.某个数的平方恰好=x，输出该数；2.某个数的平方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**2x:
                    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

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

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

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

#等差数列求和公式
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

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)