算法-数据结构-二分

算法

二分查找法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        if not nums: return -1
        left = 0
        right =len(nums)-1
        while(left<=right):
            mid=(left+right)//2
            if nums[mid]==target:
                return mid
            elif nums[mid]> target:
                right=mid-1
            else:
                left=mid+1
        return -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
37
class Solution(object):
    def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        """
        if x==0 or x==1: return x
        left =0
        right =x
        # 控制精度
        while(right-left>0.001):
            mid = (left + right) / 2
            if mid == x/mid: return mid
            if mid<x/mid:
                left=mid
            else:
                right=mid
        return "%.3f"%left



除此之外，可用用牛顿迭代法
=>  x2=x1-f(x)/f(x)`
=>  x2=(x+a/x)/2
class Solution(object):
    def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        """
        a,x1,n=x,x,0
        # 1e-9代表进度
        while(abs(x1-n)>1e-9):
            n = x1
            x1= (x1+a/x1)/2
            print(n,x1,str("%.5f"%(n-x1)))
        return x1