public class FindElementInSortedRotatedArray {
public static void main(String[] args) {
int findValue = 98;
int[] arr = {25,35,45,65,67,78,97,98,2,3,4,7,11,22,23,24};
boolean bool = checkArrIsRotated(arr);
if(bool) {
int index = findPivot(arr);
if(findValue>=arr[0] && findValue<=arr[index]) {
//first half
System.out.println(binarySearch(arr, 0, index, findValue));
}else {
//second half
System.out.println(binarySearch(arr, index+1, arr.length-1, findValue));
}
}else {
//no rotated arr
System.out.println(binarySearch(arr, 0, arr.length-1, findValue));
}
}
public static int binarySearch(int[] arr,int start,int end,int findValue) {
int mid = 0;
while(start<=end) {
mid = (start+end)/2;
if(arr[mid]==findValue) {
return mid;
}else if(findValue<arr[mid]) {
end = mid-1;
}else {
start = mid+1;
}
}
return -1;
}
public static int findPivot(int[] arr) {
int start = 0;
int end = arr.length-1;
int mid = 0;
while(start<=end) {
mid = (start+end)/2;
if(arr[mid]>arr[mid+1]) {
return mid;
}else if(arr[start]<arr[mid]) {
start = mid+1;
}else if(arr[start]>arr[mid]) {
end = mid-1;
}
}
return -1;
}
public static boolean checkArrIsRotated(int[] arr){
if(arr[0]>arr[arr.length-1]) {
return true;
}
return false;
}
}
No comments:
Post a Comment