Groupon Interview Question
Software Engineer / DevelopersCountry: United States
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.
(a) If element is greater than 0th element then
search in left array
(b) 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.
The key insight here is that doing a binary search of a rotated array is that portions of the array are still sorted, or represent another rotated array to search in. Thus, if you have the array
[7, 8, 1, 2, 3, 4, 5, 6], and you are searching for '5', this can be found in the second half of the array. So you need to tell binary search when to look in the sorted half, vs when to look in the unsorted half.
Example: If your index in binary search is 3, your value is 2, so you know the right portion will be sorted. If 5 is between 2 and the last element (6), just do binary search. Otherwise, the target would have to be in the first half (or nowhere at all). See the code below.
private static int binarySearchRotated(Integer[]list, int target, int low, int high) {
if (low > high || high < low) {
return -1; //find closest index and return it
}
int index = (low + high) / 2;
int first = list[0];
int last = list[list.length-1];
if (list[index] == target) {
System.out.println("Found " + target + "at index: " + index);
return index;
} else if (list[index] < first) { //this means we're in the (second) sorted part of the array
if (list[index] < target && target <= last) { //if the target belongs in this half, just do binary search
return BinarySearch(list, target, index+1, high);
} else { //otherwise, we have to look in the unsorted rotated portion
return binarySearchRotated(list, target, low, index-1);
}
} else { //this means we're in the first half of the array, which is still sorted
if (list[index] > target && target >= first) { //if the target belongs in the first half, just do binary search
return BinarySearch(list, target, low, index-1);
} else { //otherwise, we have to look in the unsorted rotated portion
return binarySearchRotated(list, target, index+1, high);
}
}
}
public static int find(int target, int left, int right , int [] rotate){
if (left>right){
return -1;
}
int mid = (left + right) /2 ;
if (rotate[mid] == target){
return mid;
}else if (target > rotate [mid]){
if (target>rotate[right]){
return find(target,left,mid-1,rotate);
}else if (target<rotate[right]){
return find(target,mid+1,right,rotate);
}else {
return right;
}
}else {
if (target>rotate[left]){
return find(target,left,mid-1,rotate);
}else if (target<rotate[left]){
return find(target,mid+1,right,rotate);
}else {
return left;
}
}
}
public static int find(int target, int left, int right , int [] rotate){
if (left>right){
return -1;
}
int mid = (left + right) /2 ;
if (rotate[mid] == target){
return mid;
}else if (target > rotate [mid]){
if (target>rotate[right]){
return find(target,left,mid-1,rotate);
}else if (target<rotate[right]){
return find(target,mid+1,right,rotate);
}else {
return right;
}
}else {
if (target>rotate[left]){
return find(target,left,mid-1,rotate);
}else if (target<rotate[left]){
return find(target,mid+1,right,rotate);
}else {
return left;
}
}
}
public class RotatedSortedArray {
// Array is assumed to be sorted in increasing order that has then been rotated.
// May not work if array is sorted in decreasing order and has then been rotated.
public static int search(int key, int[] arr) {
int mid;
int start = 0;
int end = arr.length - 1;
while (start <= end) {
if (arr[start] == key)
return start;
else if (arr[end] == key)
return end;
else {
mid = (start + end) / 2;
if (arr[mid] == key) {
return mid;
}
if (arr[start] < arr[mid]) { // sorted to left of mid
if ((key > arr[start]) && (key < arr[mid])) {
end = mid;
}
else if (key > arr[mid])
start = mid;
else return -1; // key is less than start
}
else // sorted to right of mid
if ((key > arr[mid]) && (key < arr[end]))
start = mid;
else // (key > array[end]) or (key < array[mid]
end = mid;
}
} //while
return -1;
} //search
public static void main (String args[]) {
int test = 0;
int[] array = {0,1,2,3,4,5};
int index = search(2, array);
System.out.println("Output of test " + test + " is " + index);
test = 1;
array[0] = 1; // array is {1,1,2,3,4,5}
index = search(1, array);
System.out.println("Output of test " + test + " is " + index);
test = 2;
array[0] = 5;
array[1] = 1;
array[2] = 1;
array[3] = 2;
array[4] = 3;
array[5] = 4; //array is {5,1,1,2,3,4}
index = search(5, array);
System.out.println("Output of test " + test + " is " + index);
test = 3;
index = search(1, array);
System.out.println("Output of test " + test + " is " + index);
/*
// Test cases for when array is in decreasing order and has then been rotated
test = 4;
for(int i=5; i>=0; i--) // array = {5,4,3,2,1,0}
array[5-i] = i;
index = search(4, array);
System.out.println("Output of test " + test + " is " + index);
test = 5;
array[0] = 0;
array[1] = 5;
array[2] = 4;
array[3] = 3;
array[4] = 2;
array[5] = 1; //array = {0,5,4,3,2,1}
index = search(3, array);
System.out.println("Output of test " + test + " is " + index); */
} // main
}; //RotatedSortedArray
package ms.searching;
public class BinarySearchOnRotatedSortedArray {
private int search(int[] input, int low, int high, int key) {
// TODO Auto-generated method stub
if (low > high) {
return -1;
} else {
int mid = (low + high) / 2;
if (input[mid] == key)
return mid;
// left is ordered
else if (input[mid] > input[low]) {
if (key < input[mid] && key >= input[low])
return search(input, low, mid - 1, key);
else
return search(input, mid + 1, high, key);
} else if (input[mid] < input[high]) {
if (key > input[mid] && key <= input[high])
return search(input, mid + 1, high, key);
else
return search(input, low, mid - 1, key);
} else if (input[mid] == input[low]) {
if (input[mid] != input[high])
return search(input, mid + 1, high, key);
else {
int result = search(input, mid - 1, low, key);
if (result == -1) {
result = search(input, mid + 1, high, key);
}
return result;
}
}
}
return -1;
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] input = { 15, 16, 19, 20, 25, 1, 3, 4, 5, 7, 10, 14 };
BinarySearchOnRotatedSortedArray bSRA = new BinarySearchOnRotatedSortedArray();
int resultIndex = bSRA.search(input, 0, input.length - 1, 14);
if (resultIndex != -1)
System.out.println("The key found at " + resultIndex);
else
System.out.println("The key not found");
}
}
/**
* Created by Samuel PC on 29/07/2015.
*/
public class SortedArrayRotated {
public static void main (String[] args) throws java.lang.Exception
{
int[] array = {4,5,6,7,9,0,1,2,3};
// get medium point
int key = 10;
int start , end;
start = 0;
end = array.length-1;
int result = findElem(array, key, start, end);
System.out.println(result);
key = 5;
result = findElem(array, key, start, end);
System.out.println(result);
key = 1;
result = findElem(array, key, start, end);
System.out.println(result);
}
public static int findElem(int arrayElements[], int key, int start , int end) {
int aux = (start+end) / 2 ;
System.out.println(key+" - "+ start+" - "+ end);
if(key == arrayElements[start]) {
System.out.println("find key");
return arrayElements[start];
}
if(key == arrayElements[end]) {
System.out.println("find key");
return arrayElements[end];
}
if(start == end || (end - start) == 1 ) {
System.out.println("key not finded");
return -1;
}
// find in the left part of the array
if(key > arrayElements[start] && key < arrayElements[aux]){
end = aux;
return findElem(arrayElements,key,start,end);
}else{
// find in the right part of the array
start = aux;
return findElem(arrayElements,key,start,end);
}
}
}
This can be done by bit modification in binary search with O(logN) time.
Please find the working code below....
INPUT : baseAddressOfArray, sizeOfArray, numToSearch.
OUTPUT : Index of element (-1 if element is not present)
- Rahul November 07, 2013