## Friday, 7 February 2014

### Search an element in a sorted and pivoted array

#### Question :

Link of Question : (GeeksForGeeks)
An element in a sorted array can be found in O(log n) time via binary search. But suppose I rotate the sorted array at some pivot unknown to you beforehand. So for instance, 1 2 3 4 5 might become 3 4 5 1 2. Devise a way to find an element in the rotated array in O(log n) time.

#### Algorithm :

Find the pivot point, divide the array in two sub-arrays and call binary search.
The main idea for finding pivot is – for a sorted (in increasing order) and pivoted array, pivot element is the only only element for which next element to it is smaller than it.
Using above criteria and binary search methodology we can get pivot element in O(logn) time

• `Input arr[] = {3, 4, 5, 1, 2}`
• `Element to Search = 1`
1. ` Find out pivot point and divide the array in two `
sub-arrays. (pivot = 2) /*Index of 5*
2. `Now call binary search for one of the two sub-arrays.`
• `If element is greater than 0th element then search in left array`
• `Else Search in right array (1 will go in else as 1 < 0th element(3))`
3. ```If element is found in selected sub-array then return index
Else return -1.```

#### Code :

```package Arrays;

/**
* Created with IntelliJ IDEA.
* User: aniket
* Date: 5/2/14
* Time: 12:08 PM
*/
public class RotatedBinarySearcher {

public int pivotedBinarySearch(int[] array, int no){

int endIndex = array.length - 1;

int pivot = findPivot(array,0,endIndex);

System.out.println("Pivot Index : " + pivot);

if(pivot == -1){    //Array is just sorted and not rotated
return binarySearch(array,0,endIndex,no);
}

if(array[pivot] == no){
return pivot;
}
else if(array[0] <= no){    //If number is greater than array[0] then it is must be left side of pivot
return binarySearch(array,0,pivot-1,no);
}
else {
return binarySearch(array,pivot+1,endIndex,no);
}
}

private int findPivot(int [] array, int start, int end){

if(start > end){
return -1;
}

if(start == end){
return start;
}

int mid = (start + end) / 2;

if(mid > start && array[mid] < array[mid-1]){
return mid - 1;
}
if(mid < end && array[mid] > array[mid + 1]){
return mid;
}

if(array[mid] <= array[start]){
return findPivot(array, start, mid-1);
}
else {  //array[mid] > array[end]
return findPivot(array, mid + 1, end);
}
}

private int binarySearch(int[] array, int start, int end, int number){

if(start > end){
return -1;
}

int mid = (end + start)/2;

if(array[mid] == number){
return mid;
}

if(number < array[mid]){
return binarySearch(array, start, mid - 1, number);
}
else{
//number > array[mid]
return binarySearch(array, mid + 1, end, number);
}
}

public static void main(String args[]){

int[] array = new int[]{3,4,5,1,2};
int searchIndex = new RotatedBinarySearcher().pivotedBinarySearch(array,1);
System.out.println("Number is at index : " + searchIndex);

}

}
```

#### Output :

Pivot Index : 2
Number is at index : 3

t> UA-39527780-1