// 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
Congratulations @spydo! You have completed the following achievement on the Hive blockchain And have been rewarded with New badge(s)
Your next target is to reach 79000 upvotes.
You can view your badges on your board and compare yourself to others in the Ranking
If you no longer want to receive notifications, reply to this comment with the word
STOPCheck out our last posts:
Support the HiveBuzz project. Vote for our proposal!