Given: an array x of N elements, sorted in ascending order and an integer a Try to find a in x. 1. if a is in x: return its position 2. if a is not in x: return the position, where to insert a in x, such that x remains sorted

Note: Question is pretty simple but there are lots of test cases to cover if you find any test case is not working , feel free to comment.

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 x[]=new int[]{2, 6, 8, 10,13};
  int a=11;
        System.out.println(search(x,a));
}
public static int search(int x[], int a)
{
       if(x==null || x.length==0) return 0;
     
       int pos=-1;
       int l=0;
       int length=x.length;
       int r=length-1;
     
       if(a<x[0])
       return 0;
     
       if(a>x[length-1])
       return length;
       if(r<=0)
        return 0;
       if(1==length){
        if(a>x[0])
        return 1;
        else if(a<=x[0])
        return 0;
       }
     
       // [2, 6, 8, 10]   values 0 , 7 , 5 , 9 , 11
       if(l<=r)
       {
         while(l<=r)
         {
           int mid=l+((r-l)/2);
           System.out.println("l= " + l + " mid = " + mid + " r= " + r);
           if(x[mid]==a)
              return mid;
           else if(x[mid] > a && x[mid-1]<a)
                  return mid;
           else if(x[mid] < a && x[mid+1]> a)
                  return mid+1;
           else if(a<=x[mid-1])
                r=mid-1;
           else if(a>=x[mid+1])
                l=mid+1;
          }
      }
        return pos;
}
}

Run Here http://ideone.com/YuA70F

TC O(logn)

SC O(1)