代码随想录——数组

• 给定一个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;
    }
    //这一份代码就比较完美，已经彻底理解了二分法，我起码在今天写出这一份代码的时候是彻底理解了二分法，所有的条件我都明白了，未来看到这里希望我还是能够像今天一样彻底理解