Home > Algorithms > Binary Search in a sorted rotated array

Binary Search in a sorted rotated array

November 28, 2011


public class RotatedBinarySearch
{
private long[] input ={ 8, 9, 10, 1, 2, 3, 4, 5, 6, 7 };
private long searchElement = 8;

public RotatedBinarySearch()
{
System.out.println("Element found at index ::" + rotatedSearch(input, 0, input.length - 1,searchElement));
}

public int rotatedSearch(long[] values, int start, int end, long x)
{
int middle = (start + end) / 2;
long startVal = values[start];
long midval = values[middle];
long endVal =  values[end];


if (startVal == x)
{
return start;
}
else if (endVal == x)
{
return end;
}
else if (end - start == 1)
{
return -1;
}

if (startVal <= midval)
{
if (x <= midval && x >= startVal)
{
return rotatedSearch(values, start, middle, x);
}
else
{
return rotatedSearch(values, middle, end, x);
}
}
else if (midval <= endVal)
{
if (x >= midval && x <= endVal)
{
return rotatedSearch(values, middle, end, x);
}
else
{
return rotatedSearch(values, start, middle, x);
}
}
else
{
return -1;
}
}

public static void main(String[] args)
{
new RotatedBinarySearch();
}
}

Advertisements
Categories: Algorithms
%d bloggers like this: