LeetCode刷題704-簡單-二分查找前言一、題目描述二、題目解析三、代碼結語

文章目錄

• 前言
• 一、題目描述
• 二、題目解析
• 三、代碼
• 結語

算法作為極其重要的一點，是大學生畢業找工作的核心競争力，是以為了不落後與人，開始刷力扣算法題！

第一遍，不求最優解，但求能過！！！

📢 ： ❤布小禅❤ 📢 作者專欄： ❤Python❤ ❤Java❤ 這是我刷第 7/100 道力扣簡單題

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

難度：簡單

1. 普通想法

   設定一個變量接收答案，初始化值為-1

   使用周遊，判斷相等

   相等就給變量重新指派為該索引

2. Python關鍵字和内置函數

   使用in關鍵字和index()函數

   判斷目标值target是否存在在數組/清單中

   如果在，就使用index()函數傳回索引

3. 使用二分查找法左

   典型的二分查找法

   使用二分查找求出最後的索引後

   判斷目标值與元素是否相等

   不相等傳回-1

   相等傳回索引

1. 普通想法（暴力解法）

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        """
        給定一個 n 個元素有序的（升序）整型數組 nums 和一個目标值 target  
        寫一個函數搜尋 nums 中的 target，如果目标值存在傳回下标，否則傳回 -1
        難度：**簡單**
        :param nums:
        :param target:
        :return:
        """
        ans=-1
        for i in nums:
            if target==i:
                ans= nums.index(i)
        return ans      

1. in關鍵字與index()函數

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        ans = 0
        if target in nums:
            ans = nums.index(target)
        else:
            ans = -1
        return ans
      

1. 二分查找

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        """
        給定一個 n 個元素有序的（升序）整型數組 nums 和一個目标值 target  
        寫一個函數搜尋 nums 中的 target，如果目标值存在傳回下标，否則傳回 -1
        難度：**簡單**
        :param nums:
        :param target:
        :return:
        """
        start = 0
        end = len(nums) - 1
        while start < end:
            mid = (start + end) // 2
            if target > nums[mid]:
                start = mid + 1
            else:
                end = mid
        if target==nums[start]:
            return start
        else:
            return -1      

二分查找法為最優解法，占用記憶體和運作時間都占優

堅持最重要，每日一題必不可少！