大前端

前端学习之家-大前端

Leetcode-704 二分查找 题解笔记

题目:


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

示例 1:

输入: nums = [-1,0,3,5,9,12], target = 9     
输出: 4       
解释: 9 出现在 nums 中并且下标为 4     

示例 2:

输入: nums = [-1,0,3,5,9,12], target = 2     
输出: -1        
解释: 2 不存在 nums 中因此返回 -1        

思路


该题目给出该数组为有序,并且强调没有重复元素,否则查找出的元素下表一定不唯一,因此如果符合这两个条件,我们就可以用二分查找
写二分法的区间的定义,一般有两种写法,左闭右闭即[left, right],或者是左闭右开即[left, right)

二分法的第一种写法

第一种写法,也就是左闭右闭的写法[left, right],因此需要注意一下:

  • while(left <= right) 要使用 <=,因为 left == right 是有意义的
public int search(int[] nums, int target) {

        //有序miss-
        if (target > nums[nums.length - 1] || target < nums[0]){
            return -1;
        }

        int low = 0, high = nums.length - 1;
        while (low <= high){
            int mid = low + (high - low) >> 1;
            if (mid < target){
                low = mid + 1;
            }else if (mid > target){
                high = mid - 1;
            }else {
                return mid;
            }
        }
        return -1;
    }

第二种写法

也就是[left, right]
代码如下:

public int search(int[] nums, int target) {

        if(nums[0] > target || nums[nums.length - 1] < target)
            return -1;

        int low = 0, high = nums.length;
        while (low < high){

            //miss-
            int mid = low + (high - low) >> 1;
            if(target < nums[mid]){
                high = mid - 1;
            }else if (target < nums[mid]){
                low = mid + 1;
            }else {
                return mid;
            }
        }
        return -1;
    }

本题重点

对 low,high 的边界处理

发表评论:

Copyright Your WebSite.Some Rights Reserved.