rajeshp
BAN USERsince the array is strictly increasing first then strictly decreasing, therefore for the increasing part of the array if, i+1=j then definitely
a[i]<a[j] and for decreasing part a[j]<a[i],
we can use modified binary search to search the array.
consider the array
int[] arr = new int[] {1,3,5,7,19,221,132,56,8,6,4,2,1,-3,-17};
here we need to find k such that, for three consecutive elements i, k, j, a[i]<a[k] and a[k] > a[j]
step 1 :
so, first we need to find the ending of increasing part of the array, lets the end index of increasing part as k.
use a modified binary search to find k
int findK(int[] arr, int low, int high)
{
if(arr.length<=2)
return -1;
int mid=(low+high)/2;
if(low==mid|| mid+1==high )
return -1;
if(arr[mid]>arr[mid-1] && arr[mid]>arr[mid+1])
return mid;
int n1= findK(arr, low, mid);
int n2= findK(arr, mid, high);
if(n1!=-1)
return n1;
if(n2!=-1)
return n2;
return -1;
}
step 2 :
Now search the increasing part of array using binary search
BinarySearch(int[] arr, low, k)
step 3:
and decreasing part using binarysearch
BinarySearch(int[] arr, k+1, high)
sum all the above steps in a single wrapper function
int searchIncresingDecreasingArray(int[] arr, int N)
{
int k = findK(arr, 0, arr.length);
//now search only increasing array using binarysearch
int res = binarySearch(arr, 0, k, N,true);
if(res!=-1)
return res;
else
return binarySearch(arr, k+1, arr.length, N,false);
}
it would be better if people start discussing the approach and algorithms and then paste the sample code.
- rajeshp August 16, 2012