leetcode题目链接:https://leetcode-cn.com/problems/binary-search/
public int search(int[] nums, int target) { int left=0; //区间左闭右闭方法 [] //int right=nums.length-1; // while(left<=right){ // int middle=left+(right-left)/2; // if (nums[middle]<target){ // left=middle+1; // }else if(nums[middle]>target){ // right=middle-1; // }else{ // return middle; // } // } // return -1; //区间左闭右开方法 [ ) int right=nums.length; while(left<right){ int middle=left+(right-left)/2; if (nums[middle]<target){ left=middle+1; }else if(nums[middle]>target){ right=middle; }else{ return middle; } } return -1; }
https://www.bilibili.com/video/BV1d54y1q7k7?spm_id_from=333.999.0.0
假如target为X。题目中已说明元素不会重复,且target不一定在数组中。
那么我们的isBlue条件可以确定为第一个小于target的元素,即nums[middle]<target; 退出while循环返回的值为right。那么nums[right]要么等于target,要么大于target。我们再判断一下nums[right]是否对等于target,如果等于就返回right,否则就返回-1.
但是代码中有一个点需要注意(也是提交代码时候才发现):当数组中所有的元素为蓝色区域时。退出while循环返回的right值为N,而数组元素的小标为N-1;此时如果判断nums[right]target时,就会报告数组越界。解决办法是加一个判断,如代码中所示:if(rightnums.length||nums[right]!=target)。
public int search(int[] nums, int target) { // 五点七边的方法 int left =-1; int right =nums.length; while(left+1!=right){ int middle=left+((right-left)/2); if (nums[middle]<target){ left=middle; }else{right=middle;} } if(right==nums.length||nums[right]!=target){ return -1; }else{ return right; } }