一定是二分,那什么时候left和right要移动呢?
假设有两条一维坐标index[0,1,2,3,4,5,6,…,+无穷]和data[-无穷,…,-2,-1,0,1,2,3,4,5,…,+无穷]
index表示数组的下标从0开始,data表示数组里面放的数据:
由于nums[0]=-3,将0和-3连线
由于nums[1]=-1,将1和-1连线
由于nums[2]=1,将2和1连线
由于nums[3]=3,将3和3连线
由于nums[4]=5,将4和5连线
并且移动两条坐标将3和3这条连线变成竖直,如图所示:
由于数组是递增的,所以:
可以发现3左边的indexLeft,都有indexLeft>=nums[indexLeft]
3右边的indexRight,都有indexRight<=nums[indexRight]
所以根据这两个判断条件,每次可以确定index和data相同的元素在左边还是在右边
class Solution {
public int getNumberSameAsIndex(int[] nums) {
if(nums==null || nums.length==0) return -1;
int left=0,right=nums.length-1;
while(left<=right){
int mid=left+(right-left)/2;
if(mid==nums[mid]) return mid;
if(mid<nums[mid]){
//目标在左边
right=mid-1;
}else{
//目标在右边
left=mid+1;
}
}
return -1;
}
}