「704. 二分查找 」| leetcode 刷題009

題目1

統計字元串中的單詞個數，這裡的單詞指的是連續的不是空格的字元。

請注意，你可以假定字元串裡不包括任何不可列印的字元。

示例:

輸入: "Hello, my name is John"

輸出: 5

解答

class Solution(object):
    def countSegments(self, s):
        """
        :type s: str
        :rtype: int
        """
        return len(s.split())
           

split()函數可以分割任何符号，包括逗号，句号，什麼亂七八糟的符号。相比較來說，其他語言可沒有這麼簡潔的用法。

題目2

給定一個 n 個元素有序的（升序）整型數組 nums 和一個目标值 target ，寫一個函數搜尋 nums 中的 target，如果目标值存在傳回下标，否則傳回 -1。

示例 1:

輸入: nums = [-1,0,3,5,9,12], target = 9

輸出: 4

解釋: 9 出現在 nums 中并且下标為 4

示例 2:

輸入: nums = [-1,0,3,5,9,12], target = 2

輸出: -1

解釋: 2 不存在 nums 中是以傳回 -1

提示：

• 你可以假設 nums 中的所有元素是不重複的。
• n 将在 [1, 10000]之間。
• nums 的每個元素都将在 [-9999, 9999]之間。

剛開始我沒有看見題目，自己一看這麼簡單，順手就寫了

class Solution(object):
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        if target in nums:
            return nums.index(target)
        else:
            return -1
           

寫完之後我覺得不對，再看看題目，說的是二分查找。所謂二分查找就是把清單一分為二，在左右兩邊查找，确定元素區間之後再次一分為二，直至确定元素。

class Solution(object):
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        left, right = 0, 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
           

這才是這道題要考察的二分查找。

檢視執行結果36ms。