Find a given integer value in a given shifted array
//Binary Search with shifted arrays
//Programming Language- JAVA
//my code
public class Binary_search_with_shift {
static int find_shift(int[] n) {
int left=0;
int right=n.length-1;
if(n[left]>=n[right]) {
while(right>left) {
int mid = (right+left)/2;
if(n[mid]>n[mid+1]) {
return mid+1;
}else if(right == left+1) {
return 0;
}
if(n[mid]>=n[right]) {
left=mid;
}
if(n[mid]<n[right]) {
right=mid;
}
}
return 0;
}else {
return 0;
}
}
static int search(int[] numbers, int target, int left, int right) {
if(numbers[left] == target) {
return left;
}
if(numbers[right] == target) {
return right;
}
while(right>=left) {
int mid=(left+right)/2;
if(numbers[mid]==target) {
return mid;
}
if(numbers[mid]>target) {
right = mid-1;
}
if(numbers[mid]<target) {
left = mid+1;
}
}
return -1;
}
static int bsearch_with_shift(int[] numbers, int target) {
if(numbers.length<=0) {
return -1;
}
int shift = find_shift(numbers);
if(shift == 0) {
int left = 0;
int right = numbers.length-1;
int val = search(numbers, target, left, right);
return val;
}
int left1 = 0;
int right1 = shift-1;
int val1 = search(numbers, target, left1, right1);
if(val1 >= 0) {
return val1;
}else {
int left2 = shift;
int right2 = numbers.length-1;
int val2 = search(numbers, target, left2, right2);
return val2;
}
}
public static void main(String[] args) {
int[] n = {3,5,8,12,13,15,21,23,29,32,36,40};
int[] m = {5,8,12,13,15,21,23,29,32,36,40,3};
int[] s = {21,23,29,32,36,40,3,5,8,12,13,15};
int[] u = {40,3,5,8,12,13,15,21,23,29,32,36};
int[] q = {32,36,40,3,5,8,12,13,15,21,23,29};
int[] k = {23,29,32,36,40,3,5,8,12,13,15,21};
int[] l = {23,29,32,36,40,3,5,8,12,13,15};
int[] w = {29,32,36,40,3,5,8,12,13,15,21,23};
int[] a = {5,5,5,5,5,5,5,5,5,5,5,5};
int[] b = {5,5,5,5,5,5,5,2,3,3,4,5};
int[] c = {5,5,5,5,5,2,3,3,4,5,5,5};
int[] h = {5};
int[] p = {};
System.out.println(bsearch_with_shift(m, 40)); //10
System.out.println(bsearch_with_shift(s, 8)); //8
System.out.println(bsearch_with_shift(a, 5)); //0
System.out.println(bsearch_with_shift(a, 6)); //-1
System.out.println(bsearch_with_shift(c, 1)); //-1
System.out.println(bsearch_with_shift(h, 5)); //0
System.out.println(bsearch_with_shift(h, 6)); //-1
System.out.println(bsearch_with_shift(p, 6));//-1
}
}