leetcode 二分查找 - easy

objc94 發(fā)布于2019-07-30 17:44 / 781人閱讀

摘要：如果目標值不存在于數(shù)組中，返回它將會被按順序插入的位置。也因為是排序的數(shù)組，所以可以考慮二分法。計算并返回的平方根，其中是非負整數(shù)。輸入輸出說明的平方根是由于返回類型是整數(shù)，小數(shù)部分將被舍去。是一個非負整數(shù)，并且在位有符號整型的范圍內(nèi)。

有時候會抽時間看看題目，鍛煉一下
簡單記錄下二分查找吧，會持續(xù)更新的啊哈~~~
僅供參考，路過看下就行，歡迎交流~

第35題

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

想法：簡單粗暴一點，因為是排序數(shù)組，所以直接for遍歷就可以了。

class Solution(object):
    def searchInsert(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        # 如果target大于max(nums),則直接插入最后位置
        for i in range(0,len(nums)):
            if nums[i] >= target:
                return i
        return len(nums)

但是若目標值若是最大的，則得等循環(huán)len(nums)遍才能找到，時間復(fù)雜度高。也因為是排序的數(shù)組，所以可以考慮二分法。

class Solution(object):
    def searchInsert(self, nums, target):
        left = 0
        right = len(nums)-1
        while left <= right :
            # 中間的數(shù)
            middle = (right-left) / 2 + left
            if nums[middle] == target:
                return middle
            elif nums[middle] > target : # 即target在左邊
                right = middle - 1 
            else :
                left = middle + 1
        return left

第69題：x的平方根

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

 由于返回類型是整數(shù)，小數(shù)部分將被舍去。

class Solution(object):
    def mySqrt(self, x):
        l, r = 0, x
        while l <= r:
            mid = l + (r-l)//2
            if mid * mid <= x < (mid+1)*(mid+1):
                return mid
            elif x < mid * mid:
                r = mid
            else:
                l = mid + 1

第367題：有效的完全平方數(shù)

給定一個正整數(shù) num，編寫一個函數(shù)，如果 num 是一個完全平方數(shù)，則返回 True，否則返回 False。
說明：不要使用任何內(nèi)置的庫函數(shù)，如 sqrt。
輸入：16 輸出：True
輸入：14 輸出：False

class Solution:
    def isPerfectSquare(self, num):
        """
        :type num: int
        :rtype: bool
        """
        left = 0
        right = num
        #tag = None
        while left <= right :
            mid = (right-left)//2  + left   # 減少循環(huán)次數(shù)
            val = mid *mid 
            if val == num :
                #tag = True
                return True
            elif val > num :
                #tag = False
                right = mid - 1 
            else:
                #tag = False
                left = mid + 1
        #return tag  
        # 注釋掉部分減少運行時間，其次通過val來減少中間運算
        return False

第441題：排列硬幣

你總共有 n 枚硬幣，你需要將它們擺成一個階梯形狀，第 k 行就必須正好有 k 枚硬幣。
給定一個數(shù)字 n，找出可形成完整階梯行的總行數(shù)。
n 是一個非負整數(shù)，并且在32位有符號整型的范圍內(nèi)。
n = 5
硬幣可排列成以下幾行:
¤
¤ ¤
¤ ¤
因為第三行不完整，所以返回2.

n = 8
硬幣可排列成以下幾行:
¤
¤ ¤
¤ ¤ ¤
¤ ¤
因為第四行不完整，所以返回3.

class Solution(object):
    def arrangeCoins(self, n):
        if n == 0:
            return 0
        left = 1
        right = n/2
        while left <= right:
            mid = (right-left)/2+left
            total = (mid * (mid+1)) / 2
            if total > n:
                right = mid - 1
            elif n - total < mid + 1:
                return mid
            elif n-total == mid + 1:
                return mid+1
            else:
                left = left + 1
        return left