二分法

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

class Solution(object):
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        len_nums = len(nums)
        left = 0
        right = len_nums - 1   # 最右侧的索引
        while(left <= right):
            mid = int((left + right) / 2)

            if nums[mid] == target:
                return mid
            if nums[mid] > target:
                right = mid - 1   # mid 已经不被考虑了 所以 向内收缩 -1
            if nums[mid] < target:
                left = mid + 1   # mid 已经不被考虑了 所以 向内收缩 +1

return -1

相关推荐