首页 > 其他分享 >代码随想录——数组

代码随想录——数组

时间:2024-06-10 17:01:14浏览次数:31  
标签:right target nums int 代码 随想录 mid 数组 left

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

    //这个题说实话从逻辑上来看实在是太简单了,但是为什么每一次我写起来都感觉隐隐约约有点问题,为什么呢?就是因为我的问题没有得到解决,我只是一味的去逃避,要真正的系统性的提高,就不能只知道正确答案是怎么写的,还要知道错误答案是怎么错的。
    //现在来理清自己的思路:首先二分查找是需要三个指针的,对应着left,mid,right;然后对于这个有序的数组,我们要做的就是让mid指的数和target比较,然后如果target大,就修改left,target小,就修改right,相等就返回mid。我的问题是什么呢?什么时候返回-1,这个问题是要解决的。
    //理清了思路之后,现在就是把逻辑转化为代码了
    public static int search(int nums[],int target)
    {
        int left=0,right=num.length()-1;
       
        while(left<right)
        {
             mid=(left+right)/2;//这里为了防止溢出还有优化的可能
            if(target>nums[mid])
            {
                left=mid;
            }else if{
                target<nums[mid]
                right= mid;
            }else{
                return mid;
            }
        }
        return -1;
    }

上面是我自认为正确的代码,其实我这个代码是有很多局限的,甚至上,在思路上都是错的,因为从出发点上就错了。作为一个小白,最需要做的就是无条件相信教材上的思路,现在我只需要背诵记忆,等到有一定基础就可以提出自己的想法了,这才是学习的路径。把代码随想录的思想全部背下来,我所有的操作都要和他一模一样。

代码随想录的逻辑(记忆背诵)
  • 二分法易错点

    • while中left是小于还是小于等于right

    • if中nums[mid]>target时,这个right是等于mid还是mid-1

  • 循环不变量

    • 要明确二分法的区间,是左闭右闭还是左闭右开,这个是很重要的,忽略了这个那么所有的东西都会出问题,很少有人定义左开右闭,因此忽略(现在不理解没关系,之后慢慢会理解)

  • 左闭右闭

    left = 0;right=nums.length()-1;
    while(left<=right)
    {//在左闭右闭里面,left和right相等是合法区间,因此要在while里面进行循环查找
    mid=(left+right)/2;
    if(nums[mid]>target){
        right=mid-1;//因为在左闭右闭的区间里,已经明确了mid所指的不是target,因为right就没有必要等于mid,而是取mid-1
    }else if(nums[mid]<target){
        left=mid+1;
    }else{
        return mid;
    }
    }
    return -1
    上述代码并不规范,类似伪代码
    • 左闭右开

      int left = 0,right=nums.length()-1;
      int mid;
      while(left<right)
      {
          mid=(left+right)/2;//这一步可以优化
          if(nums[mid]>target)
          {
              right=mid;
          }else if(nums[mid]<target)
          {
              left=mid+1;
          }else
          {
              return mid;
          }
          return -1;
      }
      //这一份代码就比较完美,已经彻底理解了二分法,我起码在今天写出这一份代码的时候是彻底理解了二分法,所有的条件我都明白了,未来看到这里希望我还是能够像今天一样彻底理解

标签:right,target,nums,int,代码,随想录,mid,数组,left
From: https://blog.csdn.net/weixin_48937413/article/details/139575513

相关文章