題目

給定一個含有 n 個無重復(fù)整數(shù)的升序列表 nums 和一個目標(biāo)值 target ，請查找 nums 中的 target，如果目標(biāo)值存在返回下標(biāo)，否則返回 -1。

例如：

給定一個列表 nums ：[-1, 0, 3, 5, 9, 12]，target = 9
返回結(jié)果：4

給定一個列表 nums ：[-1, 0, 3, 5, 9, 12]，target = 2
返回結(jié)果：-1

實現(xiàn)思路

在本題中說明了 nums 是一個有序列表，并且列表中元素?zé)o重復(fù)，因此我們可以考慮使用 二分查找 來實現(xiàn)。

• 定義2個變量：left、right ，分別表示左邊界下標(biāo)和右邊界下標(biāo)，left 默認(rèn)值為第一個元素下標(biāo)，即 left = 0，right 默認(rèn)值為最后一個元素下標(biāo)，即 right = len(nums) - 1
• 首先，計算出 left 和 right 之間的中間元素下標(biāo) mid = (left + right) // 2，并將中間元素 nums[mid] 與目標(biāo)值 target 進行比較，總共分為3種情況
• 第一種情況，如果中間元素等于 target ，那么直接返回 mid 即可
• 第二種情況，如果中間元素大于 target ，那么說明 target 出現(xiàn)在中間元素的左側(cè)，所以需要修改右邊界下標(biāo) right = mid - 1
• 第三種情況，如果中間元素小于 target ，那么說明 target 出現(xiàn)在中間元素的右側(cè)，所以需要修改左邊界下標(biāo) left = mid + 1
• 當(dāng) left 小于等于 right ，我們就對以上幾步進行重復(fù)操作，如果在列表中查找到 target ，那么就可以直接返回對應(yīng)下標(biāo)，如果最后 left 大于 right 時還沒有查找到 target ，那么就說明列表中不存在 target ，停止循環(huán)并返回 -1

我們可以發(fā)現(xiàn)，二分查找的邏輯其實不難，但它在實現(xiàn)過程中，涉及到不少邊界條件，很容易弄亂，因此我們在實現(xiàn)過程中必須對變量的區(qū)間考慮清楚。

代碼實現(xiàn)--while循環(huán)，非遞歸

class Solution:
    def binary_search(self, nums, target):
        left, right = 0, len(nums) - 1
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] > target:
                right = mid - 1
            elif nums[mid] < target:
                left = mid + 1
            else:
                return mid
        return -1

代碼實現(xiàn)--遞歸

class Solution:
    def binary_search(self, nums, target):
        return self.binary_search_recursive(nums, target, 0, len(nums) - 1)

    def binary_search_recursive(self, nums, target, left, right):
        if left > right:
            return -1
        mid = (left + right) // 2
        if nums[mid] > target:
            return self.binary_search_recursive(nums, target, left, mid - 1)
        elif nums[mid] < target:
            return self.binary_search_recursive(nums, target, mid + 1, right)
        else:
            return mid

更多Python編程題，等你來挑戰(zhàn)：Python編程題匯總（持續(xù)更新中……）