Binary search in an array with boolean values

Question

I have an array with boolean values. But sequence of elements like these: first go true values, and then false values. For example,

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

So now we have a sorted array with boolean values, starting with true values if true value exists.

The task is to find first false element.
I created a class with search method using binary search algorithm.

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

It is not working correct, i.e. sometimes it is returning previous element of searched one.
Finding element by searching iteratively is also not good idea, because array's size could be really big, and it will take much time.

Edit: Actually I need to search in MySQL database table. But table size is too big, and finding required row takes to much time, I want to use binary search algorithm for fastening.

Edit: MySQL table size more than 45 million rows. It takes about 30 seconds when searching required row by SQL query, no matter I added index to the column or not. Furthermore adding index in boolean doesn't give any effect.
When I use binary search it takes about 10 milliseconds. So I want the above method to be corrected.
Edit: For instance, I have DB table called "INFORMATION". And it has two columns "INFO" (TEXT) and "CHECKED" (BOOLEAN). Initial values of "INFO"s are false. And I will get first unchecked info, and get N rows starting from unchecked, then I will check them and mark them true. Process will be repeated until there is no unchecked infos.

And searching about the bug when the size is an odd number ? I don't see a question so I write this one ;) — AxelH
– AxelH, Commented Jan 31, 2017 at 14:08
Why would you use Binary search to find the first false element?!! — Null
– Null, Commented Jan 31, 2017 at 14:14
@Null because it's asymptotically faster than a linear probe...? — Andy Turner
– Andy Turner, Commented Jan 31, 2017 at 14:15

Vanguard · Accepted Answer · 2017-02-01 07:04:34Z

5

I amended the Xin Huang answer and simplified the code a bit:

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

So now the method is returning index of first false element in the array if element found, and negative value if element not found.

edited Feb 1, 2017 at 7:04

answered Feb 1, 2017 at 6:53

Vanguard

1,3961 gold badge16 silver badges30 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

greedy52 · Accepted Answer · 2017-02-01 05:44:42Z

1

During loop, if booleanValue is false

if low = mid, starting point and ending point meets, we found what we need
else high = mid since mid is definitely a potential candidate

Modified as below:

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

answered Feb 1, 2017 at 5:44

greedy52

1,41510 silver badges8 bronze badges

2 Comments

greedy52 Over a year ago

This code still has a bug when all values == true. You may want to update your return for special case mid == array.length -1.

Vanguard Over a year ago

please change if (low == mid) { break;} to if (low == mid) return mid, and last return to return -(low + 1);

Collectives™ on Stack Overflow

Binary search in an array with boolean values

2 Answers 2

Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related