// Rotating array is the array with is shorted be can be rotated a number of times.
// {1,2,3,4,5,6,7,8,9} => simple array.
// {9,1,2,3,4,5,6,7,8} => One Rotation
// {8,9,1,2,3,4,5,6,7} => 2nd Rotation
// {7,8,9,1,2,3,4,5,6} => 3rd Rotation
// => with each rotation just last element come at first.
// Find the pivot of array (larget number index)
// Apply binary search at right if not found apply at left.
// Our task is to find the pivot
public class RotatingAarrayTarget {
public static void main(String[] args) {
int[] arr = {7,8,9,10,2,3,4,5,6};
int target = 3;
int ourPivod = findPivod(arr);
System.out.println(ourPivod);
}
static int findPivod(int[] arr){
int start = 0;
int end = arr.length - 1;
while (start <= end ){
int mid = start + (end - start)/2;
// case 1
if (arr[mid] > arr[mid+1]){
return mid;
}
// case 2
if (arr[mid-1] > arr[mid]){
return mid - 1;
}
// case 3 and 4
if (arr[start] >= arr[mid]){
end = mid - 1;
}else{
start = mid +1;
}
}
return -1;
}
}
// Case 1: When mid < mid + 1 => mid is pivot
// Case 2: When mid-1 > mid; then mid-1 is pivot
// Case 3: When start >= mid then all number right of mid is smaller so we ignore them.
// Case 4: When start < mid then first half is soted array, then we ignore the left side and work with right parts
// for case 4 use start = mid +1;
// 3:10: of video
