[9.5] Find string in sorted array of strings

1. Example

SORTED array of strings => Binary Search

find "ball" in ["at","","","","ball","","","car","","","dad","",""] will return 4
find "ballcar" in ["at","","","","","ball","car","","","dad","",""] will return -1


2. Implementation
Use ordinary binary search
1. hit an empty string, advance to the next non-empty string
2. If there is no next non-empty string, search the left half

if (str=="") 

{ 

     for ( int i=0; i < strings.length; i++ ) 

     {

           if (strings[i] == "") return i; 

     } 

     return -1; 

}

public int search(String[] strings, String str)
{




    // validate the input
    if ( strings == null || str == null )
       return -1;




    if (str=="")
    {
          for ( int i=0; i < strings.length; i++ ) 
          {
              if (strings[i] == "") return i;
          }


          return -1;



    }




    return search(strings, str, 0, strings.length - 1);



}

public int search(String[] strings, String target, int l, int r)
{
   
    
    while( l <= r  )
    {
 

         

          // Ensure there is something at the end
          while ( l  <= r && strings[r] == "" )
                --r;
          // The block was empty, so fail
          if ( r < l)
                return -1;




          int m = (l+r)/2;
          



          while (strings[m] == "")
                ++m;



          // NOTE: binary Search
          int r = strings[m].compareTo(target);
          if ( r == 0 )
               return m;
          if ( r < 0)// at < ball(target)
               l = m+1;
          else   // ball(target) < car
               r = m-1;




    }



    return -1;



}

3.Similar Ones