在有空字符串中的有序字符串数组中查找

题目

有个排序后的字符串数组，其中散布着一些空字符串，编写一个方法，找出给定字符串(肯定不是空字符串)的索引

思路

• 既然字符串有序，可以采用二分法；
• 字符串的大小比较可以采用（strcmp）；
• 选取mid中间值时，如果遇到空字符串，使其往下移动一位；

代码实现

function indexOf($arr, $target) {
    $begin = 0;
    $end = count($arr) - 1;
    while ($begin <= $end) {
        $indexOfMid = $begin + (($end - $begin) >> 1);
        while($arr[$indexOfMid] == "") {
            $indexOfMid++;
            if ($indexOfMid > $end) {
                return false;
            }
        }
        //strcmp: 按字节比较字符串
        if (strcmp($arr[$indexOfMid], $target) > 0) {
            $end = $indexOfMid - 1;
        } else if(strcmp($arr[$indexOfMid], $target) < 0){
            $begin = $indexOfMid + 1;
        } else {
            return $indexOfMid;
        }
    }
    return false;
}

$arr = ["a", "", "ac", "", "ad", "b", "", "ba"];
echo indexOf($arr, "ac");
结果： 2