Linkedin Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Phone Interview
We can append same array to original array and apply the binary search and return index % n(original array length)
eg: A = [4 5 6 1 2 3] n = 6
modified array B = [4 5 6 1 2 3 4 5 6 1 2 3]
suppose we want to search for 5. On first iteration we will get the mid = 6 (Assuming 1 based index) Then it will search in right half and recursively it will find 5 at location 8. Return position as 8%6 = 2.
It works.
Bro why do you think it doesn't?
A little work around will make it work.
3 is at location 6, so 6%6 = 0. But 0 is not valid index(Chetan assumed 1 based indexing) so 0==>N and hence the location is 6.
Try this:
public class RotatedSortedArray {
public static void main(String[] args) {
int arr[] = { 4, 5, 6, 7, 8, 9, 10, 0, 1, 2, 3 };
int L = 0, H = arr.length - 1;
int mid = (L + H) / 2;
int key = 10;
while (L <= H) {
mid = (L + (H - L) / 2);
if (arr[mid] == key) {
System.out.println("Found at " + mid);
break;
} else {// bottom half is sorted
if (arr[L] < arr[mid]) {
if (key < arr[mid])
H = mid - 1;
else
L = mid + 1;
} else if (arr[H] > arr[mid]) {
if (key > arr[mid])
L = mid + 1;
else
H = mid - 1;
}
}
}
}
}
/* package whatever; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
public static void main (String[] args) throws java.lang.Exception
{
int arr[] = {4,5,6,1,2,3};
System.out.println(modifiedBinarySearch(arr, 5, 0, arr.length -1 ));
System.out.println(modifiedBinarySearch(arr, 2, 0, arr.length -1 ));
System.out.println(modifiedBinarySearch(arr, -1, 0, arr.length -1 ));
}
public static boolean modifiedBinarySearch(int arr[], int val, int low, int high){
if(low > high)
return false;
int mid = (low + high) / 2;
if(arr[mid] == val)
return true;
else{
if(arr[low]<arr[mid] && val < arr[mid] && val > arr[low]){
return modifiedBinarySearch(arr, val, low, mid);
}else{
return modifiedBinarySearch(arr, val, mid+1, high);
}
}
}
}
Sorry I am posting revised version. Previous one is not correct. I removed it but it seems that the post is not removed instantly. Here we go:
#include<stdlib.h>
#include<stdio.h>
int binarySearch(int * arr, int low, int high, int item)
{
if (low > high) {
return -1;
}
int mid = (low + high) / 2;
if (item < arr[mid]) {
binarySearch(arr, low, mid, item);
}
else if (item > arr[mid]) {
binarySearch(arr, mid + 1, high, item);
}
else {
return mid;
}
}
int binarySearch_modified(int * arr, int low, int high, int length, int item)
{
if (low > high) {
return -1;
}
int mid = (low + high) / 2;
if (item < arr[mid % length]) {
binarySearch_modified(arr, low, mid, length, item);
}
else if (item > arr[mid % length]) {
binarySearch_modified(arr, (mid + 1), high, length, item);
}
else {
return mid % length;
}
}
int main() {
int arr[6] = { 1, 2, 3, 4, 5, 6 };
int index = -1;
index = binarySearch(arr, 0, 5, 3);
if (index == -1) {
printf("not found\n");
}
else {
printf("found at index=%d\n", index);
}
int arr_shifted[6] = { 3, 4, 5, 6, 1, 2};
int shiftedBy = 4;
index = binarySearch_modified(arr_shifted, 0+shiftedBy, 5+shiftedBy, 6, 1);
if (index == -1) {
printf("not found\n");
}
else {
printf("found at index=%d\n", index);
}
}
elements = [16,17,18,19,20,10,11,12,13]
def binarySearch(val,low,high):
print "Value = "+str(val)+"low = "+str(low)+"high = "+str(high)
if low > high :
return -1
mid = ( low+high ) / 2
print "mid = "+str(mid)+"------------------"
if elements[mid] == val :
return mid
if elements[low] <= elements[mid] :
if elements[low] <= val <= elements[mid] :
return binarySearch(val,low,mid-1)
else :
return binarySearch(val,mid+1,high)
elif elements[mid] <= elements[high] :
if elements[mid] <= val <= elements[high] :
return binarySearch(val,mid+1,high)
else :
return binarySearch(val,low,mid-1)
return -1
print str(binarySearch(13,0,len(elements)-1))
elements = [16,17,18,19,20,10,11,12,13]
def binarySearch(val,low,high):
print "Value = "+str(val)+"low = "+str(low)+"high = "+str(high)
if low > high :
return -1
mid = ( low+high ) / 2
print "mid = "+str(mid)+"------------------"
if elements[mid] == val :
return mid
if elements[low] <= elements[mid] :
if elements[low] <= val <= elements[mid] :
return binarySearch(val,low,mid-1)
else :
return binarySearch(val,mid+1,high)
elif elements[mid] <= elements[high] :
if elements[mid] <= val <= elements[high] :
return binarySearch(val,mid+1,high)
else :
return binarySearch(val,low,mid-1)
return -1
print str(binarySearch(13,0,len(elements)-1))
In regular binary search we always go to the left sub array if pivot is greater than search element otherwise to the right sub array.
For rotated binary search, the idea is to check in which sub-array we need to continue the binary search based on certain boundary value checks. The below binary search works for both regular
and rotated arrays.
public int rotatedBinarySearch(int [] arr, int lowIndex, int highIndex, int toSearch) {
int m = (highIndex + lowIndex) / 2;
if (arr[m] == toSearch) {
return m;
}
// Guard against values not in array
if (highIndex - lowIndex == 0) {
return Integer.MIN_VALUE;
}
if (arr[lowIndex] <= arr[m]) {
if (arr[lowIndex] <= toSearch && toSearch <= arr[m]) {
return search(arr, lowIndex, m - 1, toSearch);
} else {
return search(arr, m + 1, highIndex, toSearch);
}
}
if (arr[m] <= arr[highIndex]) {
if (arr[m] <= toSearch && toSearch <= arr[highIndex]) {
return search(arr, m + 1, highIndex, toSearch);
} else {
return search(arr, lowIndex, m - 1, toSearch);
}
}
return Integer.MIN_VALUE;
}
java> rotatedBinarySearch(new int [] {7, 9, 10, 11, 1, 3, 5}, 0, 6, 4);
java.lang.Integer res48 = -2147483648
java> rotatedBinarySearch(new int [] {7, 9, 10, 11, 1, 3, 5}, 0, 6, 5);
java.lang.Integer res49 = 6
java> rotatedBinarySearch(new int [] {7, 9, 10, 11, 1, 3, 5}, 0, 6, 3);
java.lang.Integer res50 = 5
java> rotatedBinarySearch(new int [] {7, 9, 10, 11, 1, 3, 5}, 0, 6, 7);
java.lang.Integer res51 = 0
java> rotatedBinarySearch(new int [] {7, 9, 10, 11, 1, 3, 5}, 0, 6, 9);
java.lang.Integer res52 = 1
java> rotatedBinarySearch(new int [] {7, 9, 10, 11, 1, 3, 5}, 0, 6, 77);
java.lang.Integer res53 = -2147483648
java> rotatedBinarySearch(new int [] {7, 9, 10, 11, 1, 3, 5}, 0, 6, 4);
java.lang.Integer res54 = -2147483648
java> rotatedBinarySearch(new int [] {7, 9, 10, 11, 1, 3, 5}, 0, 6, 2);
java.lang.Integer res55 = -2147483648
java> rotatedBinarySearch(new int [] {7, 9, 10, 11, 1, 3, 5}, 0, 6, 2);
java.lang.Integer res56 = -2147483648
Here is C++ version of solution
#include <iostream>
using namespace std;
bool find_array(int *input, int s, int e, int target)
{
if (s> e)
return false;
int half = s+ (e-s)/2;
if (input[half] == target)
return true;
if (input[half] <target)
{
if (input[e] >= target)
s = half+1;
else
e = half-1;
} else {
if (input[s] <= target)
e = half -1;
else
s = half +1;
}
return find_array(input, s, e, target);
}
int main()
{
int input[6] = { 4,5,6,1,2,3};
cout << "find 1 = " <<find_array(input, 0, 5, 1)<<endl;
cout << "find 5 = " << find_array(input, 0, 5, 5)<<endl;
cout<< " find 2 = " << find_array(input, 0, 5, 2)<<endl;
cout<< " find 0 = " << find_array(input, 0,5, 0)<<endl;
return 1;
}
public static void main(String[] args) {
int[] arr = {2,3,4,5,6,7,8,9,10,11};
int[] arr1 = {3,4,5,6,7,8,9,10,11,2};
int arrayRotatedIndex = rotatedIndex(arr1, 0, arr1.length-1);
int originalArray = findElement(arr, 0, arr.length-1, 4);
System.out.println(arr[originalArray]);
System.out.println(arr1[originalArray+arrayRotatedIndex-arr.length]);
}
private static int findElement(int[] arr,int low,int high,int value) {
int mid = -1;
while(low <= high) {
mid = low + (high - low) / 2;
if(arr[mid] == value) return mid;
if(arr[mid] > value) {
high = mid - 1;
}
if(arr[mid] < value) {
low = mid + 1;
}
}
return mid;
}
public static int rotatedIndex(int[] arr1, int low, int high) {
int rotatedIndex = -1;
while(low <= high) {
int mid = low + (high - low) / 2;
if(arr1[mid] > arr1[low] && arr1[mid] > arr1[high]) {
low = mid;
}
else if(arr1[mid] < arr1[low] && arr1[mid] < arr1[high]) {
high = mid;
}
else {
rotatedIndex = mid + 1;
break;
}
}
return rotatedIndex;
}
Code for the binary search
import java.util.Arrays;
/**
* Created by Sameer on 1/3/2017.
*/
class BinarySearchRotation {
public static int search(int[] arr, int elem){
return binSearch(arr, elem, 0, arr.length - 1);
}
private static int binSearch(int[] arr, int elem, int start, int end){
while(start <= end){
int mid = (start + end) / 2;
// Found element
if(arr[mid] == elem){
return mid;
}
else{
// Check if mid is less than elem
if(arr[mid] < elem){
if(arr[start] >= arr[end] && elem > arr[end]){
end = mid - 1;
}
else{
start = mid + 1;
}
}
// Go to the left of mid
else{
// Go to right of mid
if(elem <= arr[end] && arr[mid] > arr[end]){
start = mid + 1;
}
else{
end = mid - 1;
}
}
}
}
// Return -1 if element is not found
return -1;
}
}
Tests:
import org.junit.Test;
import static org.junit.Assert.*;
/**
* Created by Sameer on 1/3/2017.
*/
public class BinarySearchRotationTest {
@Test
public void search() throws Exception {
// Test 1
int[] arr = {1, 3, 4, 5, 6, 8};
int elem = 6;
assertEquals("Search failed", 4, BinarySearchRotation.search(arr, elem));
elem = 5;
assertEquals("Search failed", 3, BinarySearchRotation.search(arr, elem));
elem = 4;
int[] arr1 = {5, 6, 7, 8, 2, 3, 4};
assertEquals("Search failed", 6, BinarySearchRotation.search(arr1, elem));
elem = 6;
int[] arr2 = {6, 7, 1, 2, 3, 4, 5};
assertEquals("Search failed", 0, BinarySearchRotation.search(arr2, elem));
elem = 10;
assertEquals("Search failed", -1, BinarySearchRotation.search(arr2, elem));
}
}
Binary Search:
#include <iostream>
using namespace std;
int getIndex(int* array, int val, int start, int end) {
if (start >= end) {
if (array[start] == val) return start;
else return -1;
}
int mid = (start+end)/2;
if (array[mid] == val)
return mid;
if (array[mid] > val)
return getIndex(array, val, start, mid);
return getIndex(array, val, mid+1, end);
}
int findNum(int* array, int len, int val) {
return getIndex(array, val, 0, len-1);
}
int main()
{
int array[] = {1, 2, 3, 4, 5, 6};
int val = 3;
printf("index of %d = %d\n", val, findNum(array, 6, val));
val = 1;
printf("index of %d = %d\n", val, findNum(array, 6, val));
val = 7;
printf("index of %d = %d\n", val, findNum(array, 6, val));
return 0;
}
followup:
#include <iostream>
using namespace std;
int getIndex(int* array, int val, int start, int end) {
if (start >= end) {
if (array[start] == val) return start;
else return -1;
}
int mid = (start+end)/2;
if (array[mid] == val)
return mid;
if (array[mid] > val) {
if (array[start] > val)
return getIndex(array, val, mid+1, end);
return getIndex(array, val, start, mid);
}
else {
if (array[start] > val)
return getIndex(array, val, start, mid);
return getIndex(array, val, mid+1, end);
}
return -1;
}
int findNum(int* array, int len, int val) {
return getIndex(array, val, 0, len-1);
}
int main()
{
int array[] = {4, 5, 6, 1, 2, 3};
int val = 2;
printf("index of %d = %d\n", val, findNum(array, 6, val));
val = 6;
printf("index of %d = %d\n", val, findNum(array, 6, val));
val = 5;
printf("index of %d = %d\n", val, findNum(array, 6, val));
return 0;
}
Yeah, this doesn't work. I think we need a logn algorithm to find the maximum of the array(the place where the array was broken) and then use that in the search.
I think this work in log(n) time.
1. Find the shift by doing a binary search on the shifted array (say k index).
2. Now doing a binary search in the two halves of the array depending upon the 'val' in the interval (1,k) and (k+1,n) as both will be sorted only.
Assuming it is rotated only once.
Python solution
def find_rotation(array, start, end):
if start == end:
return start
mid = (start + end) / 2
if array[mid] < array[mid-1] return mid
if array[mid] > array[0]:
return find_rotation(array, mid+1, end)
else:
return find_rotation(array, start, mid-1)
First I discover which half is correctly ordered. If the desired value is within the range of this correct half, call the binary search into it. Otherwise, call into the other half. When the binary search comes into a subvector that has a correct ordering, it behaves as the regular binary search.
int f(const std::vector<int> &V, int s, int e, int x)
{
if (e < s) return -1;
int m = (s+e)/2;
int mid = V[m];
if (mid == x) return m;
if (V[s] <= mid) {
if (x >= V[s] and x <= mid) {
return f(V, s, m-1, x);
}
return f(V, m+1, e, x);
}
if (x >= mid and x <= V[e]) {
return f(V, m+1, e, x);
}
return f(V, s, m-1, x);
}
2 binary searches.
1) find the pivot point using binary search using the first element in the rotated array. Key property is that the numbers between the first element and the pivot element is ascending.
2) after finding the pivot point, use binary search on the left or right subarray from the pivot point to find the element you're looking for.
Total running time: O(logn)
Actually this can be reduced to one binary search. Just have to modify the if statement for going left or right of mid to be based also on the first value of the array. This method also uses the fact that the values between the first index and the pivot index are incrementing.
if ((arr[mid] > searchValue && arr[0] > searchValue) || (arr[mid] < searchValue && arr[0] > searchValue )
search right side of mid index
else if ((arr[mid] > searchValue && arr[0] < searchValue) || (arr[mid] < searchValue && arr[0] < searchValue ))
search left side of mid
bool hasElement (int *Array, int value, int start, int end)
{
if (Array == NULL || start > end || start < 0 || end < 0) return false;
if (start == end && Array[start] != value) return false;
int mid = (start + end) / 2;
if (Array[mid] == value) return true;
bool isSortedLeftSide = false;
bool isSortedRightSide = false;
if (start >= (mid-1) || (start < (mid-1) && Array[start] < Array[mid-1]) )isSortedLeftSide = true;
if ((mid+1) == end || ((mid+1) < end && Array[mid+1] < Array[end])) isSortedRightSide = true;
ASSERT(isSortedLeftSide || isSortedRightSide); //At least one side should be sorted
if (!isSortedRightSide)
{
int lastValue = Array[end];
for (int i = end - 1; i >= mid+1; i--)
{
if ( Array[i] > lastValue )
{
mid = i;
break;
}
}
}
else if (!isSortedLeftSide)
{
int previousValue = Array[mid -1];
for (int i = mid-2; i >= start; i--)
{
if ( Array[i] > previousValue )
{
mid = i;
break;
}
}
}
if (Array[mid] == value) return true;
if (start <= mid-1 && value >= Array[start] && value <= Array[mid-1])
{
return hasElement (Array, value, start, mid-1);
}
else if (mid+1 <= end && value >= Array[mid+1] && value <= Array[end])
{
return hasElement (Array, value, mid+1, end);
}
else
{
return false;
}
}
We can use rotated binary search as below:
public void rotatedBinSearch()
{
int arr[] = { 4, 5, 6, 7, 8, 9, 10, 0, 1, 2, 3 };
int L = 0, H = arr.length - 1;
int mid = (L + H) / 2;
int key = 10;
while (L <= H) {
mid = (L + (H - L) / 2);
if (arr[mid] == key) {
System.out.println("Found at " + mid);
break;
} else {// bottom half is sorted
if (arr[L] < arr[mid]) {
if (key < arr[mid])
H = mid - 1;
else
L = mid + 1;
} else if (arr[H] > arr[mid]) {
if (key > arr[mid])
L = mid + 1;
else
H = mid - 1;
}
}
}
}
public class BinarySearch {
public static int binarySearch(final int[] array, final int value) {
return binarySearchHelper(array, value, 0, array.length - 1);
}
private static int binarySearchHelper(final int[] array,
final int value, final int left, final int right) {
if (left > right)
return -1; // not found
int mid = (left + right) / 2;
if (value == array[mid]) {
return mid;
} else if (value < array[mid]) {
return binarySearchHelper(array, value, left, mid - 1);
} else { // (value > array[mid])
return binarySearchHelper(array, value, mid + 1, right);
}
}
public static int binarySearchShifted(final int[] array, final int value) {
return binarySearchShiftedHelper(array, value, 0, array.length - 1);
}
private static int binarySearchShiftedHelper(final int[] array,
final int value, final int left, final int right) {
if (left > right)
return -1; // not found
int mid = (left + right) / 2;
if (value == array[mid]) {
return mid;
} else if ((array[left] <= array[mid] && (array[left] <= value && value < array[mid]))
|| (array[mid] <= array[right] && !(array[mid] < value && value <= array[right]))) {
return binarySearchShiftedHelper(array, value, left, mid - 1);
} else {
return binarySearchShiftedHelper(array, value, mid + 1, right);
}
}
public static void main(String[] args) {
test(6);
test(7);
}
private static void test(int count) {
int array[] = new int[count]; // {10, 20, ... 10*COUNT}
for (int i=0; i<count; i++) {
array[i] = 10 * (i+1);
}
int VALUE_MIN = 8;
int VALUE_MAX = 10 * count + 2;
printArray(array);
for (int value = VALUE_MIN; value <= VALUE_MAX; value++) {
int index = binarySearch(array, value);
boolean pass = ((index >= 0 && (value % 10 == 0)) || (index < 0 && (value % 10 != 0)));
if (!pass) {
System.out
.println("*** FAIL ***"
+ " value = "
+ value
+ ((index >= 0) ? (" index = " + index)
: " Not Found"));
}
}
System.out.println();
for (int shift = 0; shift < count; shift++) {
for (int i = 0; i < count; i++) {
array[i] = 10 * (((shift + i) % count) + 1);
}
printArray(array);
for (int value = VALUE_MIN; value <= VALUE_MAX; value++) {
int index = binarySearchShifted(array, value);
boolean pass = ((index >= 0 && (value % 10 == 0)) || (index < 0 && (value % 10 != 0)));
if (!pass) {
System.out.println("*** FAIL ***"
+ " value = "
+ value
+ ((index >= 0) ? (" index = " + index)
: " Not Found"));
}
}
System.out.println();
}
}
private static void printArray(int[] array) {
System.out.print("array[] = { ");
for (int i = 0; i < array.length; i++) {
System.out.print(array[i]);
System.out.print(" ");
}
System.out.println("}");
}
}
public static boolean search(int[] array, int low, int high, int shiftedBy, int lookupElement) {
if(low>high) return false;
int mid = (low + high)/2;
int shiftedIndex = mid - shiftedBy;
if(shiftedIndex < 0) {
shiftedIndex = array.length + shiftedIndex;
}
if(array[shiftedIndex]==lookupElement) return true;
else if(array[shiftedIndex]<lookupElement) return search(array, mid+1, high, shiftedBy, lookupElement);
else return search(array, low, mid-1, shiftedBy, lookupElement);
}
- dev. February 20, 2015