题目

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

Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.

You must write an algorithm with O(log n) runtime complexity.

要点

  • nums已经是升序排列
  • 时间复杂度: O(logn)

代码

  1. class Solution:
  2.     def search(self, nums: List[int], target: int) -> int:
  3.         l=0
  4.         r=len(nums)-1
  5.         while(l<=r):
  6.             mid = (l+r)//2
  7.             if nums[mid]<target:
  8.                 l = mid+1
  9.             elif nums[mid]>target:
  10.                 r = mid-1
  11.             else:
  12.                 return mid
  13.         return -1

分析

二分查找(binary search)是算法中必须掌握的基础算法之一。其特征是每次查找都会把查找范围缩短一半，故时间复杂度为O(logn)，默认以2为底。举例：nums = [1,2,3,4,5,6,7,8], 最坏情况下需要log(8)=3次即可找到结果。

一点细节

python中 // 符号会返回整数结果（向下取整）