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)

Given a element, find the strictly greater element in sorted array - 1st post for 2k14

E.g. if array is // [ a, c, d, h, k, l, l, l, o, u, x, z ]
//if given  m -> o
// if given k -> l


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
{
// your code goes here
System.out.println(search(new char[]{'b', 'c', 'd', 'h', 'k', 'l', 'l', 'l', 'o', 'u', 'x', 'z'},'b')) ;
}

static char search(char a[],char find)
{
   if(a==null || a.length==0)
   return ' ';// if nothing found
 
   int start=0;
   int end=a.length-1;
   if(start>end) return ' ' ; //|| find>=a[end]) return ' ';
   if(find <a[start]) return a[start];
   if(start==end && a[start]>find)
   return a[start];
   while(start<end)
   {
       int mid=start+(end-start+1)/2; //to minimize over flow
       if(mid+1<=end && find>=a[mid] && find <a[mid+1])
              return a[mid+1];
       else if(mid-1>=0 && find < a[mid] && find >= a[mid-1])
        return a[mid];
       else if(find >=a[mid])
           start=mid;
       else if( find <a[mid])
           end=mid;
       else
          return ' ';
      System.out.println("start= " + start + ":::" +  " End= " + end);
   }
   return ' ';//if nothing found , return special character
}
}

Time Complexity O(logn)
Space Complexity O(1)