蓝桥学院2019算法题2.18

 1 package recursion;
 2 
 3 /**
 4  * @author zsh
 5  * @company wlgzs
 6  * @create 2019-02-18 15:21
 7  * @Describe 题3·在有空字符串的有序字符串数组中查找
 8  * 有个排序后的字符串数组，其中散布着一些空字符串，
 9  * 编写一个方法，找出给定字符串（肯定不是空字符串）的索引。
10  */
11 public class Main6 {
12 
13     /**
14      * 查找给定字符串（肯定不是空字符串）的索引
15      * @param arr 待查找的字符数组
16      * @param p 待查找的字符串
17      * @return 字符串在数组中的位置索引
18      */
19     static int indexOf(String[] arr,String p){
20         int begin = 0;
21         int end = arr.length-1;
22         while (begin <= end){
23             int middle = ((begin+end) >>> 1);
24             while (arr[middle].equals("")){
25                 middle++;
26                 //注意
27                 if (middle > end){
28                     return -1;
29                 }
30             }
31             if (arr[middle].compareTo(p) > 0){
32                 end = middle -1;
33             }else if (arr[middle].compareTo(p) < 0){
34                 begin = middle + 1;
35             }else {
36                 return middle;
37             }
38         }
39         return -1;
40     }
41 
42     public static void main(String[] args) {
43         String[] arr = new String[]{"a","","ac","","ad","b","","ba"};
44         System.out.println(indexOf(arr,"b"));
45         System.out.println(indexOf(arr,"abc"));
46     }
47 }