[数据结构与算法] LeetCode每日一题（二分查找）

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> LeetCode每日一题（二分查找） -> 正文阅读

[数据结构与算法]LeetCode每日一题（二分查找）

704 题目描述：给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
在这里插入图片描述

暴力破解法

class Solution {
    public int search(int[] nums, int target) {
        for(int i=0;i<nums.length;i++){
            if(nums[i]==target) return i;
        }

        return -1;
    }
}

二分查找法

比如在一个有序的数组并且无重复元素的数组中，例如[1, 2, 3, 4, 5, 6]，需要查找3的位置就可以使用二分查找

二分法的思想很简单，因为整个数组是有序的，数组默认是递增的。首先选择数组中间的数字和需要查找的目标值比较：

如果相等最好，就可以直接返回答案了
如果不相等：如果中间的数字大于目标值，则中间数字向右的所有数字都大于目标值，全部排除；如果中间的数字小于目标值，则中间数字向左的所有数字都小于目标值，全部排除

数组长度是偶数还是奇数这个真的不重要，不影响怎么排除的问题，无非是多排除一个数字或者少排除一个数字。真正影响的是中间那个数字到底该不该加入下一次的查找中，也就是边界问题

左闭右闭[left, right]：

class Solution {
    public int search(int[] nums, int target) {
        int left=0;
        int right=nums.length-1;

        while(left<=right){
            int middle=(left+right)/2;

            if(nums[middle]>target) right=middle-1;
            else if(nums[middle]<target) left=middle+1;
            else return middle;
        }

        return -1;
    }
}

左闭右开[left, right)：

class Solution {
    public int search(int[] nums, int target) {
        int left=0;
        int right=nums.length;

        while(left<right){
            int middle=(left+right)/2;

            if(nums[middle]>target) right=middle;
            else if(nums[middle]<target) left=middle+1;
            else return middle;
        }

        return -1;
    }
}

二分法最重要的两个点：循环条件和区间赋值

循环条件能够控制区间赋值的边界；区间赋值left和right的关系决定了循环能不能继续

left = 0, right = nums.length-1 ——> while(left <= right)
left = 0, right = nums.length ——> while(left < right)

35 题目描述：给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。请必须使用时间复杂度为 O(log n) 的算法。
在这里插入图片描述

二分查找法

class Solution {
    public int searchInsert(int[] nums, int target) {
        int left=0;
        int right=nums.length-1;
        int middle=-1;

        while(left<=right){
            middle=(left+right)/2;
            if(nums[middle]<target) left=middle+1;
            else if(nums[middle]>target) right=middle-1;
            else return middle;
        }

        if(left==middle+1) return left;
        return right+1;
    }
}

如果没有找到对应的值，则右指针会指向最大小于target的值，左指针指向最小大于target的值

34 题目描述：给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值 target，返回 [-1, -1]。你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
在这里插入图片描述

二分查找法

二分查找的基本思想：在一个区间范围里看处在中间位置的元素的值nums[mid]与目标元素target的大小关系，进而决定目标值落在哪一个部分里

目标元素target在有序数组中很可能存在多个

使用二分查找方法看到的处在中间位置的元素的值nums[mid]恰好等于目标元素target的时候，还需要继续查找下去

比较容易陷入的误区是线性查找，正确的做法是继续二分查找

不推荐：

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int left=0;
        int right=nums.length;
        int middle=-1;

        int[] pos=new int[2];

        while(left<right){
            middle=(left+right)/2;

            if(nums[middle]>target) right=middle;
            else if(nums[middle]<target) left=middle+1;
            else{
                int mid=middle;
                while(middle>=0&&nums[middle]==target) {
                    left=middle;
                    middle--;
                }
                while(mid<nums.length&&nums[mid]==target){
                    right=mid;
                    mid++;
                } 
                pos[0]=left;
                pos[1]=right;
                return pos;
            }
        }

        
        pos[0]=-1;
        pos[1]=-1;
        return pos;
    }
}

牛顿迭代法

class Solution {
    int s;
    
    public int mySqrt(int x) {
        s=x;
        if(x==0) return 0;
        return ((int)(sqrts(x)));
    }
    
    public double sqrts(double x){
        double res = (x + s / x) / 2;
        if (res == x) {
            return x;
        } else {
            return sqrts(res);
        }
    } 
}

$这种算法的原理很简单，我们仅仅是不断用 (x,f(x))的切线来逼近方程 x^2?a=0的根。根号 a 实际上就是 x^2?a=0的一个正实根，这个函数的导数是 2x。也就是说，函数上任一点 (x,f(x)) 处的切线斜率是 2x。那么，x?f(x)/(2x)就是一个比 x 更接近的近似值。代入 f(x)=x^2?a得到 x?(x^2?a)/(2x)，也就是 (x+a/x)/2。$

二分查找法

class Solution {
    public int mySqrt(int x) {
        int l = 0, r = x, ans = -1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if ((long) mid * mid <= x) {
                ans = mid;
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return ans;
    }
}