Search in Bitonic Array!

 https://www.interviewbit.com/problems/search-in-bitonic-array/

// Function for binary search in ascending part of array 
int asc(vector<int> A, int low, int high, int B) 
{ 
   while (low <= high) 
   { 
       int mid = low + (high - low) / 2; 
       if (A[mid] == B) 
           return mid; 
       else if (A[mid] > B) 
           high = mid - 1; 
       else
           low = mid + 1; 
   } 
    return -1; 
} 
  
// Function for binary search in descending part of array 
int dsc(vector<int>A, int low, int high, int B) 
{ 
   while (low <= high) 
   { 
       int mid = low + (high - low) / 2; 
       if (A[mid] == B) 
           return mid; 
       else if (A[mid] < B) 
           high = mid - 1; 
       else
           low = mid + 1; 
   } 
    return -1; 
} 
int Solution::solve(vector<int> &A, int B) {
    int ans = -1;
    int start = 0, end = A.size() - 1;
    int mid = 0;
    while(start<=end)
    {
        mid = start + (end-start)/2;
        if(A[mid]>A[mid+1] && A[mid]>A[mid-1])
            break;
        else if(A[mid]<A[mid+1] && A[mid-1]<A[mid])
            start = mid+1;
        else
            end = mid-1;
    }
    if(A[mid] == B)
        return mid;
    int l = asc(A,0,mid-1,B);
    int r = dsc(A,mid+1,A.size()-1,B);
    if(l!=-1 || r!=-1)
        return l!=-1?l:r;
    return -1;
}


 

Comments

Post a Comment

Popular posts from this blog

Perfect Peak of Array

  Given an integer array A of size N . You need to check that whether there exist a element which is strictly greater than all the elements on left of it and strictly smaller than all the elements on right of it. If it exists return 1 else return 0 .  https://www.interviewbit.com/old/problems/perfect-peak-of-array/ int Solution::perfectPeak(vector<int> &A) { int ans=-1; int l[A.size()]; int r[A.size()]; l[0]=A[0]; r[A.size()-1]=A[A.size()-1]; for(int i=1;i<A.size();i++){     l[i] = max(A[i],l[i-1]); } for(int i=A.size()-2;i>=0;i--){     r[i] = min(A[i],r[i+1]); } for(int i=1;i<A.size()-1;i++){     if(A[i]>l[i-1]&&A[i]<r[i+1]){         return 1;     } } if(ans==-1){     return 0; } }  
Read more

Is Rectangle?

 https://www.interviewbit.com/old/problems/is-rectangle/ int Solution::solve(int A, int B, int C, int D) {      if (((A==B)&&(C==D))||((A==C)&&(B==D))||((A==D)&&(B==C))){         return 1;     }else{         return 0;     } }  
Read more

Sort array with squares!

 https://www.interviewbit.com/old/problems/sort-array-with-squares/      vector<int> Solution::solve(vector<int> &arr) {         int mid=0;     for(int i=0;i<arr.size();i++)     {         if(arr[i]>=0)         {             mid=i;             break;         }     }     int i=mid-1,j=mid;     vector<int>res(arr.size());     int k=0;     while(i>=0 && j<arr.size())     {         if((arr[i]*arr[i])<(arr[j]*arr[j]))         {             res...
Read more