02-13：leetcode重刷4之二分查找

二分查找

1、求平方根（精确到整数、精确到小数位）

2、有序数组的查找

1、不精确到小数的平方根

代码如下：

class Solution:

    def mySqrt(self, x: int) -> int:

                l=0

                r=x

                ans=-1

                while l<=r:

                    m=(l+r)//2

                    if m*m<=x:

                        ans=m

                        l=m+1

                    else:

                        r=m-1

                return ans

2、精确到小数点后几位

import math

def sqrtmy(n,a): #二分查找法 a是精确度

    if n<=0:

        return n

    l=0*0.0

    r=n*1.0

    while l<=r:

       mid=(l+r)/2.0

       if abs(mid*mid-n)<=a:

          return mid

       elif mid*mid<n:

               l=mid

       else:

               r=mid

    return -1

2、有序数组的查找

leetcode:704. 二分查找

class Solution:

    def search(self, nums: List[int], target: int) -> int:

        l=0

        r=len(nums)-1

        while l<=r:

            m=(l+r)//2

            if nums[m]==target:

                  return m

            elif nums[m]<target:

                 l=m+1

            else:

                r=m-1

        return -1