CareerCup

Its easy you can implement binary search . You do two binary search. First for elements at even position(index_even = 2*i) and another one for elements at odd position(index_odd = 2*i+1).

public static int alternateBinarySearch(int[] array, int i)
    {
        int low1=0, high1= (int)Math.ceil(((double)array.length)/2)-1, mid1;
        int low2=0, high2= array.length/2-1, mid2;
        
        if(array[array.length-1]==i)
         return array.length-1;
        
        if(array[array.length-2]==i)
         return array.length-2;
        
        if(array[0]==i)
         return 0;
        
        if(array[1]==i)
         return 1;
        
        while(low1<high1-1||low2<high2-1)
        {
            mid1=(high1+low1)/2;
            mid2=(high2+low2)/2;
            
            if(array[2*mid1]==i)
                return mid1*2;
            else if(array[2*mid1]>i)
                high1= mid1;
            else
                low1= mid1;
            
            if(array[2*mid2+1]==i)
                return mid2*2+1;
            else if(array[2*mid2+1]>i)
                high2= mid2;
            else
                low2= mid2;
        }
        return -1;
    }

here is what we can do
low1 = 0;  // even indexes
low2 = 1; // odd indexes
len = arr.length;
if (len%2 ==)  {
    high1 = len-2;
    high2  = len-1;
}
else {
      high1 = len-1;
      high2  = len-2;
}

// search in even indexes
int idx = search (low1, high1, value, true);  // true to say it is for even indexes
if (idx == -1) {
   idx = search (low2, high2, value, false)
}
return idx;
}

int search (int low, int high, int value, boolean even) {
     while (low < high) {
          int mid = (low+high)/2;
          if (even && mid %2 != 0) {  // if index is even and mid is not even, make mid as even
               mid = mid-1;
          }
          else if (!even & mid%2 == 0) { // if index is odd and mid is even, make mid as odd.
              mid = mid -1;
          }
          if (a[mid] == value) {
               return mid;
          }
           else if (a[mid] < value) {
               low = mid+2;
          }
          else {
               high = mid-2;
           }
           return search (low, high, value);
      }
      return -1;

--> we are calling binary search two times , first on elements at even position and then for elements at odd position
--> we can also merge both the conditions in one call but that was getting complex and wouldn;t improve performance anyway....

Time complexity here is O(logn) , Space complexity O(1)

#include<stdio.h>
#include<stdlib.h>
 
int search(int arr[],int element,int start,int end); 
 
int main()
{
        int arr[] = {12,2,16,5,18,32,33,38,34,39};
        int length = sizeof(arr)/sizeof(int);
        
        //suppose we are searching for 16;
        int element = 39;
        
        printf("\n Search Trace \n");
        
        // We will apply binary search seperately on list of elements at even position
        //and then at list of elements at odd position
        
        
        
        int evenStart = 0;  //start of list of even elements
        int oddStart = 1;   //start of list of odd elements
        int end = length-1;
        int evenEnd;    //end of list of even elements
        int oddEnd;     //end of list of odd elements
        
        if(end%2==0)
        {
                evenEnd = end;
                oddEnd = end - 1;
        }
        else
        {
                oddEnd = end;
                evenEnd = end - 1;
        }
        
        
        int pos;
        
        pos = search(arr,element,evenStart ,evenEnd );
        
        if(pos == -1)
                pos = search(arr,element,oddStart,oddEnd );
        
        
        if(pos == -1)
                printf("\n\nElement not in list ");
        else
                printf("\n\nPositio of element : %d in list is %d",element,pos );
                
        return 0;
}
 
//basic binary search
 
int search(int arr[],int element,int start,int end)
{
 
        printf("Start : %d \t End : %d\n\t\t",start,end);
 
        if(start > end)
                return -1;
        
        int mid = (start + end)/2;
        
        if(start%2 == 0) //if start is even then making sure that middle element is also at even position
        {
                if(mid%2 != 0)
                        mid++;
        }
        else            //if start is odd then making sure that middle element is also at odd position
        {
                if(mid%2 == 0)
                        mid++;
        }
                
        if(element == arr[mid])
                return mid;
        
        int pos;
        
        //since we have odd and even elements we do mid+2 and mid-2 to make
        //sure start and end are always odd or even 
        
        if(element > arr[mid])
                pos = search(arr,element,mid+2,end);
        else
                pos = search(arr,element,start,mid-2);
 
        return pos;
                
}

Ouput :
Search Trace
Start : 0 End : 8
Start : 6 End : 8
Start : 10 End : 8
Start : 1 End : 9
Start : 7 End : 9


Positio of element : 39 in list is 9

int 
bsearch(int arr[], int lindex, int rindex, int target) {
    if (lindex > rindex) return -1;
    int n = (rindex - lindex) / 2 + 1;
    int mid;
    if (is_even(n)) {
         mid = (lindex + rindex) / 2 - 1;
    } else {
         mid =  (lindex + rindex) / 2;
   }
   if (arr[mid] == target) {
         return mid;
   } else if (arr[mid] > target) {
      return bsearch(arr, lindex, mid - 1);
  } else {
      return bsearch(arr, mid + 1, rindex);
  }
}

int 
search(int arr[], int n) {
    int retv = bsearch(arr, 0, n);
    if (retv >= 0) return retv;
    retv = bsearch(arr, 1, n - 1);
    if (retv >= 0) return retv;
    return -1; 

}

bool findnum(num,start,end)
if start > end return false
else
if(num == a[(start + end)/2]
return true
else if(num < a[(start + end)/2]
return findnum(num,start,(start + end)/2 -1]
else
return findnume(num,(start + end)/2 +1 , end)

This must work !!