首页 文章

使用布尔值在数组中进行二进制搜索

提问于
浏览 次
3

我有一个布尔值的数组 . 但是像这样的元素序列：首先是 true 值，然后是 false 值 . 例如，

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

所以现在我们有一个带有布尔值的排序数组，如果存在 true 值，则从 true 值开始 .

The task is to find first false element.
我使用二进制搜索算法创建了一个带有搜索方法的类 .

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);
    }
}

它不正确，即有时它返回搜索到的前一个元素 .
通过迭代搜索来查找元素也不是一个好主意，因为数组的大小可能非常大，而且需要很长时间 .

Edit: 其实我需要在MySQL数据库表中搜索 . 但是表大小太大，找到所需的行需要花费很多时间，我想使用二进制搜索算法进行紧固 .

Edit: MySQL表大小超过4500万行 . 通过SQL查询搜索所需行时大约需要30秒，无论我是否为列添加了索引 . 此外，在 boolean 中添加索引不会产生任何影响 .
当我使用二进制搜索时，大约需要10毫秒 . 所以我想要纠正上面的方法 .
Edit: 例如，我有一个名为"INFORMATION"的数据库表 . 它有两列"INFO"（TEXT）和"CHECKED"（BOOLEAN） . "INFO"的初始值为 false . 我将获得第一个未经检查的信息，并从未选中获得N行，然后我将检查它们并标记它们 true . 将重复该过程，直到没有未经检查的信息为止 .

java binary-search

2 回答

  • 3

    我修改了 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 元素的索引，如果找不到元素则返回负值 .

    回复于
  • 1

    在循环期间，如果booleanValue为false

    • 如果低=中，起点和终点相遇，我们找到了我们需要的东西

    • 其他高=中期，因为中期肯定是一个潜在的候选人

    修改如下：

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

相关问题