algorithm - 如何使用二进制搜索查找数组中的第一个非空元素？

Question

假设我有一个连续数据和连续空值的数组，例如：

0, 3, 1, 2, null, null, null

如何使用二分查找思想查找第一个空元素的索引？

Answer 1

与常规二进制搜索相同，仅将 NULL 视为值无穷大（max int），其他所有内容都视为值 0。这样数组看起来像

0, 0, 0, 0, MAX_INT, MAX_INT, MAX_INT

此时对它的第一个 MAX_INT 运行正常的二进制搜索

Answer 2

执行二进制搜索，如下所示：

• 从中间开始（就像二分查找一样）
• 当你找到一个 not-null时，向右进行二分搜索
• 当你找到 anull时，检查左边的元素
  • 如果是null，则向左二分查找
  • 如果不是 - null（或者左边没有元素，因为我们已经在最左边的元素了）我们找到了第一个的索引null

一些简单的伪代码：

int search(start, end):
  // terminating check - should always be the first null
  if start == end
    // sanity check - make sure it's correct
    assert(input[start] == null && (start == 0 || input[start-1] != null))
    return start

  mid = (start+end)/2

  if input[mid] != null
    return search(mid, end) // search right
  else if mid == 0 || input[mid-1] != null // check element to left
    return mid // found
  else
    return search(start, mid) // search left

Answer 3

在这里，使用 O(n) 的简单蛮力可能是理想的，因为在分而治之时，它同样可能会错过第一次出现的 Null。

Answer 4

这是一个用 Go 编写的示例解决方案，时间复杂度为 O(log(n))：

package main

import "fmt"

func findIn(array []int) {
    fmt.Printf("%v ", array)

    if len(array) == 0 {
        fmt.Println("Not Found")
        return
    }

    for low, high, mid := 0, len(array), len(array)/2; ; {

        // terminate search when high meets mid
        if high-mid == 1 {
            if array[mid] == -1 {
                fmt.Println(mid)
                return
            }
            if high == len(array) {
                fmt.Println("Not Found")
                return
            }
            fmt.Println(high)
            return
        }

        // search lower half if middle is -1, otherwise search upper half
        if array[mid] == -1 {
            high = mid
            mid = low + (mid-low)/2
        } else {
            low = mid
            mid = mid + (high-mid)/2
        }
    }

    fmt.Println()
}

func main() {
    findIn([]int{})
    findIn([]int{8})
    findIn([]int{-1})
    findIn([]int{8, -1, -1, -1})
    findIn([]int{8, 9, 7, -1, -1, -1})
    findIn([]int{8, 9, 7, 6, 5, 4, -1, -1})
}

输出：

[] Not Found
[8] Not Found
[-1] 0
[8 -1 -1 -1] 1
[8 9 7 -1 -1 -1] 3
[8 9 7 6 5 4 -1 -1] 6

请随时提出更好/更短的解决方案。