1 package POJ; 2  3 public class Main { 4  5     /** 6      *  7      * 11.5 Given a sorted array of strings which is interspersed with empty 8      * strings, write a method to find the location of a given string. 9      * 10      */11     public static void main(String[] args) {12         Main so = new Main();13     }14 15     public int search(String[] strs, String str) {16         if (strs == null || str == null || str.equals("")) {17             return -1;18         }19         return searchR(strs, str, 0, str.length() - 1);20     }21 22     private int searchR(String[] strs, String str, int first, int last) {23         // TODO Auto-generated method stub24         if (last < first)25             return -1;26         int mid = (first + last) / 2;27         if (strs[mid].isEmpty()) {28             int left = mid - 1;29             int right = mid + 1;30             while (true) {31                 if (left < first && right > last)32                     return -1;33                 else if (right <= last && !strs[right].isEmpty()) {34                     mid = right;35                     break;36                 } else if (left >= first && !strs[left].isEmpty()) {37                     mid = left;38                     break;39                 }40                 right++;41                 left--;42             }43         }44         if (str.equals(strs[mid]))45             return mid;46         else if (strs[mid].compareTo(str) < 0)47             return searchR(strs, str, mid + 1, last);48         else49             return searchR(strs, str, first, mid - 1);50     }51 52 }