力扣刷题|二分查找入门（Java）

75 阅读 0 评论 50 点赞

我是靠谱客的博主含糊冰淇淋，最近开发中收集的这篇文章主要介绍力扣刷题|二分查找入门（Java），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

写在前面

704. 二分查找

278. 第一个错误的版本

写在前面

刷了四五十道pat乙级题，只是博客还没来得及更新。准备入门一点力扣的题了。

做了第1题-两数之和，发现它和pat做题的思维实在不太一样。

pat有些注重解决实际问题，通常题目很长,但耐心读完题目，通常能有些思路。即便没有思绪，看过大佬的代码，明白几个要点是怎么实现的，知晓题目的逻辑，便大致能复写出来。至于时间和内存的限制，就我而言，大多是是由于数据结构的选择不到位，而不是由于算法。

力扣是什么感觉呢？题目很短，你以为很容易。就像第1题-两数之和，几乎读完题就能想到通过两次嵌套循环求解。兴高采烈地敲完短短几行代码，一看官方解答，傻眼。官方的确给出了这种解法，称之为暴力枚举。继续往下看，才是它希望你解这道题的标准做法。题目里确实说，这种降低时间复杂度的方法是进阶的。但我知道，我必须得学这种方法。毕竟力扣是很多企业面试的算法题目来源，如果出这里面的题，肯定不希望你用最原始的方法解出来。力扣较为看重时间和空间复杂度，而想降低复杂度，用到的解题思路便是完全不一样的。这就很需要发散思维了。对我来说，这是一个新的挑战，因为之前做题重在做出，而现在要重在优化了。

做了一道题后，我看到了20天算法入门计划，便想按照这个计划学起。这样的话，就没有按照算法题的顺序做了。以后更新也就不按顺序了。

关于刷题的语言，pat是用c++刷的，感觉还比较顺手。而力扣，由于目标岗位是Java后端开发，群里有些小伙伴说面试时会让用Java做题，思考了一下，我决定用Java刷力扣了。

言归正传，下面是三道二分查找的入门题目。

704. 二分查找

这应该是标准的二分查找吧附上代码先就先记下来吧。至于细节的地方，比如那个等于号，还是有些不理解qaq

class Solution {
    public int search(int[] nums, int target) {
        int mid,left=0,right=nums.length-1;
        while(left<=right){     //有等于号
            mid=left+(right-left)/2;   //假如right和left都是一个很大的数，那么right+left会溢出，而(right-left)/2+left先做减法不会溢出
            if(nums[mid]==target){
                return mid;
            }
            if(nums[mid]<target){
                left=mid+1;
            }
            else{
                right=mid-1;
            }
        }
        return -1;
    }
}