LeetCode算法第一天二分查找

我就是我 2024-04-20 22:05 53阅读 0赞

## 一、方法 ##

> 从B站看到的方法,连着刷了三个题,都遇到了问题,但都过了;
> 
> 地址:[二分查找为什么总是写错？\_哔哩哔哩\_bilibili][bilibili]

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA57q15pyJ55a-6aOO6LW3ICAg5Lq655Sf5LiN6KiA5byD_size_18_color_FFFFFF_t_70_g_se_x_16][]

这个UP主这个方法很巧妙 , 他和那种比对值得不太一样,它使用了红蓝两种颜色 来不断逼近 这个解所在的分界点 , 从而不用去考虑 要不要加等号 要不要加一的问题

--------------------

## 二、遇到的问题 ##

### 1.![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA57q15pyJ55a-6aOO6LW3ICAg5Lq655Sf5LiN6KiA5byD_size_17_color_FFFFFF_t_70_g_se_x_16][] ###

这一题 直接有这种方法 存在几个问题,

①数组中没有要找到的元素 要返回-1 这个要进行判断;

②数组中元素只有一个 因为 l的初始下标为一 导致数组越界问题

③符合条件的数字恰好在端点处，如：在【2,5】中寻找≤5的数字，最终l=1，r=2，r不移动(这个我还没有太理解 具体题目遇到了在分析 )

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

###  ###

--------------------

###  ###

### 2. ###

###  ###

### ![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA57q15pyJ55a-6aOO6LW3ICAg5Lq655Sf5LiN6KiA5byD_size_17_color_FFFFFF_t_70_g_se_x_16 1][] ###

这道题坑死我了 直接死循环 , 他给的数据 超出了 int范围 **2147483647+1=-21474883648** 我烂掉了 别的方法应该不需要转换 但这种方法 必须转成Long 因为他的范围需要加一 正好超出范围!

/* The isBadVersion API is defined in the parent class VersionControl.
          boolean isBadVersion(int version); */
    
    public class Solution extends VersionControl {
        public int firstBadVersion(int n) {
                long l=0;
                long r=(long)n+1;
                while(l+1!=r){
                    long mid=l+(r-l)/2;
                    if(!isBadVersion((int)mid)){
                        l=mid;
                       
                    }
                    else{
                        r=mid;
                      
                    }
    
                }
                return (int)r;
    }
    }

[bilibili]: https://www.bilibili.com/video/BV1d54y1q7k7?from=search&seid=4288273763794466781&spm_id_from=333.337.0.0
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA57q15pyJ55a-6aOO6LW3ICAg5Lq655Sf5LiN6KiA5byD_size_18_color_FFFFFF_t_70_g_se_x_16]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/d61db971cb89414485a5673ffd836d3b.png
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA57q15pyJ55a-6aOO6LW3ICAg5Lq655Sf5LiN6KiA5byD_size_17_color_FFFFFF_t_70_g_se_x_16]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/3a5b74cca77f4d1ca3aa8a7d7f331735.png
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA57q15pyJ55a-6aOO6LW3ICAg5Lq655Sf5LiN6KiA5byD_size_17_color_FFFFFF_t_70_g_se_x_16 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/9d61c031928542b3927f8d15b802343a.png