Sample Input:
input={6,7,8,9,0,1,2,3,4,5};
output=4
input={0,1,2,3,4,5,6,7,8,9};
output=0
public int FindStartIndex(int[] input) {
int high = input.length-1;
int low = 0;
while(low<high) {
if(input[low]<=input[high])
return low;
int mid=(high+low)/2;
if(input[mid]<input[mid+1] && input[mid]<input[mid-1])
return mid;
else if(input[mid]>input[low]) {
//left array is sorted
//start index is not in left
low=mid+1;
} else if(input[mid]<input[high]) {
//right array is sorted
//start index is not in right
high=mid-1;
}
}
return -1;
}
No comments:
Post a Comment