二分法模板

begin = 0
end = n - 1
while begin<=end:
  mid = begin + (end-begin) //2
  # 左區(qū)間
  if ...
    end = mid -1
  # 右區(qū)間
  if ...
    begin = mid + 1

題目

• Leetcode 69. Sqrt(x)

實(shí)現(xiàn) int sqrt(int x) 函數(shù)。
計(jì)算并返回 x 的平方根，其中 x 是非負(fù)整數(shù)。
由于返回類型是整數(shù)，結(jié)果只保留整數(shù)的部分，小數(shù)部分將被舍去。
示例 1: 輸入: 4 輸出: 2
示例 2: 輸入: 8 輸出: 2
說明: 8 的平方根是 2.82842..., 由于返回類型是整數(shù)，小數(shù)部分將被舍去。

解題思路：二分法、牛頓法

class Solution(object):
    def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        """
        # 二分法
        if not x :
            return 0
        if x < 4:
            return 1

        #  注意這里end從x//2開始
        start = 2
        end = x // 2
        while 1:
            i = (start + end) // 2
            # 注意判定條件
            if i ** 2 <= x and (i + 1) ** 2 >x:
                return i
            elif i ** 2 < x:
                start = i + 1
            elif i ** 2 > x:
                end = i - 1

        # 牛頓法
        r = x
        while r > x / r:
            r = (r + x / r) // 2
        return int(r)

• Leetcode 35. Search Insert Position

給定一個(gè)排序數(shù)組和一個(gè)目標(biāo)值，在數(shù)組中找到目標(biāo)值，并返回其索引。如果目標(biāo)值不存在于數(shù)組中，返回它將會(huì)被按順序插入的位置。
你可以假設(shè)數(shù)組中無重復(fù)元素。
示例 1: 輸入: [1,3,5,6], 5 輸出: 2
示例 2: 輸入: [1,3,5,6], 2 輸出: 1
示例 3: 輸入: [1,3,5,6], 7 輸出: 4
示例 4: 輸入: [1,3,5,6], 0 輸出: 0

class Solution(object):
    def searchInsert(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        # 極端值討論
        n = len(nums)
        if nums == None:
            return None
        if nums == [] or target < nums[0]:
            return 0
        if target > nums[n-1]:
            return n

        begin = 0
        end = n - 1
        while begin<=end:
            mid = (begin + end)//2
            if target == nums[mid]:
                return mid 
            elif target < nums[mid]:
                end = mid - 1
                # 注意比較target和 mid以及mid-1的值的大小
                if target > nums[mid-1]:
                    return mid
            elif target > nums[mid]:
                begin = mid + 1