forked from sambit77/Algoexpert-Java
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathShiftedBinarySearchRecursive.java
More file actions
72 lines (64 loc) · 1.82 KB
/
Copy pathShiftedBinarySearchRecursive.java
File metadata and controls
72 lines (64 loc) · 1.82 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
//Time Complexity O(log n) | Space Complexity O(log n)
import java.util.*;
class A
{
public static void main(String[] args)
{
int[] arr = new int[]{45,61,71,72,73,0,1,21,33,45};
int target = 33;
int idx = search(arr,target);
System.out.println(target+" is present in "+idx+" of array");
}
public static int search(int[] arr, int target)
{
return shiftedBinarySearch(arr,target,0,arr.length-1);
}
public static int shiftedBinarySearch(int[] arr,int target ,int left,int right)
{
//modified Binary Search
if(left > right)
{
return -1; //target element is not prsent
}
int mid = (left+right)/2;
if(arr[mid]==target)
{
return mid;
}
if(arr[mid]>target)
{
//that means target sould be to the left of mid index if it would have been sorted array
//but it is shifted so not sorted
//check if left halve is sorted or not && target is greater than arr[left]
//i.e target falls in left sub halve
if(arr[left]<arr[mid] && target >= arr[left])
{
//search in left sub halve
return shiftedBinarySearch(arr,target,left,mid-1);
}
//target falls in right subhalve
else
{
//search in rght sub halve
return shiftedBinarySearch(arr,target,mid+1,right);
}
}
else //(arr[mid]<target)
{
//targetb will fall in right sub halve if it would have been sorted
//nut it is shifted
//check if right sub halve is sorted and arr[right] is greater tah equal to target
//target falls in rights sub halve
if(arr[mid]<arr[right] && arr[right]>=target)
{
//search in right subhalve
return shiftedBinarySearch(arr,target,mid+1,right);
}
else
{
//search in left sub halve
return shiftedBinarySearch(arr,target,left,mid-1);
}
}
}
}