vlambda博客
学习文章列表

图解LeetCode #704 二分查找

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

LeetCode


官方示例


输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4

解释: 9 出现在 nums 中并且下标为 4


01 
题目解析
TOPIC ANALYSIS


二分查找的思想是对于有序排列,先将排列中的中间位置值与目标值比较,如果中间位置值等于目标值,则查找成功;如果,中间位置值大于目标值,则在前一部分继续使用该方法查找;如果,中间值小于目标值,则在后一部分继续使用该方法查找。


接下来通过图画的方式对官方示例进行讲解。


第一步:定义左右边界的值,left=0,right=nums.length-1。


需要注意的是,此处左边界的值是0,右边界的值是nums.length-1,表示是在[left...right]这个左闭右闭的区间里查找。因此,在后续的查找中要注意维护这个边界。



第二步:计算出中间值mid=left+(right-left)/2=2。


图解LeetCode #704 二分查找


此时,nums[mid]<target。所以,左边界left=mid+1=3。


图解LeetCode #704 二分查找


第三步:在[3...5]这个区间查找目标值,计算出中间值mid=left+(right-left)/2=4。


这时,nums[mid]=target。所以,查找结束,返回查找结果4。




02
动画演示
ANIMATION




03
代码实现
CODE


Java

class Solution { public int search(int[] nums, int target) { int left = 0,right = nums.length-1; while (left <= right){ int mid = left + (right-left)/2; if (nums[mid] == target){ return mid; }
if (nums[mid] - target < 0){ left = mid+1; }else { right = mid-1; } }
return -1; }}


Python

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


感谢您的学习,如有错误,欢迎留言指出。下一篇我们将学习新的内容,敬请期待。