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