有序字符串数组的查找

有个排序后的字符串数组，其中有一些空的字符串，

编写一个方法，找出给定字符串的索引。

形如：String[] arr = {"a","","ac","","ad","b","","ba"};

find "ac" 应输出 2

思路：

简单的二分法变体，当调整中间位置时考虑遇到空串的情况，

遇到空串，mid+1 或 mid-1

 注意使用String封装的 compareTo和equals方法。

（Java代码参考）

public static void main(String[] args) {

String[] arr = {"a","","ac","","ad","b","","ba"};

int res = indexOf(arr, "ac");

System.out.println(res);

}

static int indexOf(String[] arr,String target) {//target目标

int begin = 0;

int end = arr.length-1;

while(begin <= end) {

int midIndex = begin + ((end - begin)>>1);

while(arr[midIndex].equals("")) {//中值定在空串

midIndex++;//可能导致中值超过end

if(midIndex > end) {//没有找到

return -1;

}

}

if(target.compareTo(arr[midIndex]) > 0) {//目标在中值右侧

begin = midIndex + 1;

}else if(target.compareTo(arr[midIndex]) < 0) {

end = midIndex - 1;

}else {

return midIndex;

}

}

return -1;

}