11.5 排序后的字符串数组，其中散布着空字符串，编写一个方法，找出给定字符串的位置。

二分法变体，当查找到mid元素是空串时，同时向两边扩散寻找不为空串的索引作为mid，继续执行二分。

 

public class Solution {

public int search(String[] list, String str) {
if (list == null || list.length == 0 || str == null || str.isEmpty())
return -1;
return searchHelper(list, str, 0, list.length - 1);
    }

private int searchHelper(String[] a, String s, int left, int right) {

while (left <= right) {
int mid = left + (right - left) / 2;

if (a[mid].length() == 0) {
int leftNear = mid - 1;
int rightNear = mid + 1;

while (true) {
if (leftNear < left && rightNear > right)
return -1;
if (leftNear >= left && a[leftNear].length() > 0) {
                        mid = leftNear;
break;
                    }
if (rightNear <= right && a[rightNear].length() > 0) {
                        mid = rightNear;
break;
                    }

                    leftNear--;
                    rightNear++;
                }

            }

if (a[mid].equals(s))
return mid;

else if (a[mid].compareTo(s) < 0) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }

        }
return -1;

    }

public static void main(String[] args) {
        String[] stringList = { "apple", "", "", "banana", "", "", "", "carrot", "duck", "", "", "eel", "", "flower" };
        System.out.println(new Solution().search(stringList, "carrot"));
    }
}