在一个布尔值数组中进行二分查找

Question

我有一个包含布尔值的数组。但是元素的顺序如下： 首先是 true 值，然后是 false 值。 例如：

boolean[] booleans = {true, true, true, true, true,
                false, false, false, false, false, false};

现在我们有一个排序后的布尔数组，如果存在true值，则以true值开头。

任务是找到第一个false元素。
我创建了一个带有使用二分搜索算法的搜索方法的类。

public class BinarySearch {

    public static int search(boolean[] array) {

        int low = 0, mid = 0;
        int high = array.length - 1;
        boolean booleanValue;

        while (low <= high) {
            mid = (low + high) >>> 1;
            booleanValue = array[mid];
            if (booleanValue) low = mid + 1;
            else high = mid - 1;
        }

        return mid == array.length - 1 ? -(low + 1) : mid;
    }

    public static void main(String[] args) {

        boolean[] booleans = {true, true, true, true, true,
                false, false, false, false, false, false};

        int search = search(booleans);
        System.out.println("search = " + search);
    }
}

它的工作不正确，即有时返回已查找元素的前一个元素。
通过迭代搜索查找元素也不是好主意，因为数组大小可能会很大，这将花费很多时间。
编辑：实际上我需要在MySQL数据库表中搜索。 但是表格大小太大了，找到所需行需要太长时间，我想使用二进制搜索算法来加快速度。

编辑：MySQL表格大小超过4500万行。通过SQL查询查找所需行大约需要30秒，无论我是否在列中添加索引。 此外，在 boolean 中添加索引没有任何效果。
当我使用二分查找时，大约需要10毫秒。 所以我希望上述方法能够得到纠正。
编辑：例如，我有一个名为“INFORMATION”的DB表格。 它有两列“INFO”（TEXT）和“CHECKED”（BOOLEAN）。 “INFO”的初始值为false 。 我将获取第一个未检查的信息，并从未检查的信息开始获取N行，然后我将检查它们并将它们标记为true。 直到没有未检查的信息为止，将重复此过程。

- Vanguard

---

@AxelH 寻找第一个 false 元素 - Vanguard

为什么要使用二分查找来寻找第一个假元素？！！ - Null

@Null，因为它的渐近速度比线性探测更快吗？ - Andy Turner

为什么要担心算法呢？SELECT * FROM table WHERE booleanField LIMIT 1。 - Andy Turner

@pyramidPeak 对的，所以主键首先按ID排序，然后是CHECKED。为了使其快速，您希望CHECKED排在第一位（但它可能不是您想要使用的主键）。 - Andy Turner

Answer 1

我修改了Xin Huang的答案并稍微简化了代码：

public static int search(boolean[] array) {

    int low = 0, mid;
    int high = array.length - 1;
    boolean booleanValue;

    while (low <= high) {
        mid = (low + high) >>> 1;
        booleanValue = array[mid];
        if (booleanValue) low = mid + 1;
        else if (low == mid) return mid;
        else high = mid;
    }
    return -low;
}

现在该方法如果找到元素，则返回数组中第一个false元素的索引，如果未找到元素，则返回负值。

- Vanguard

Answer 2

在循环过程中，如果booleanValue为假

1. 如果low = mid，则起始点和结束点相遇，我们找到了需要的内容
2. 否则，由于mid肯定是一个潜在的候选者，所以high = mid

修改后如下：

    while (low <= high) {
        mid = (low + high) >>> 1;
        booleanValue = array[mid];
        if (booleanValue) {
            low = mid + 1;
        }
        else {
            if (low == mid) {
                break;
            }
            high = mid;
        }
    }

- greedy52

---

这段代码在所有值都为true时仍有一个错误。你可能需要更新特殊情况mid == array.length -1的返回值。 - greedy52

请将 if(low == mid) {break;} 改为 if(low == mid) return mid，并将最后一个 return 改为 return -(low + 1);。 - Vanguard