I have a hypothetical array of Booleans that contains 50 elements. The values of these booleans are unknown to me and the only way to find out the value of a specific element is to call a method and supply the element's index to it. This method is costly in terms of CPU cycles and what I am trying to do is write a code that uses the least amount of calls to this method to determine the value of a specific element.

If there is an element with a false value in this array, then all the elements before it must also be false. If there is an element with a true value in this array, then all the elements after it must also be true.

To give an example of such arrays:

[false, false, false, true, true, true, true]
[false, false, false, false]
[true, true]

The element I am looking for is, as you have guessed, the one where the changing from false to true happens, if any.

Obviously the first thing I thought of was slightly modified binary search that looks like this:

int FindFirstTrue(HypotheticalBool[] arr)
{
    int low = 0;
    int high = arr.Length - 1;
    int mid;
    while (low <= high)
    {
        mid = low   (high - low) / 2;
        if (checkArr(arr, mid))
        {
            if (!checkArr(arr, mid-1))
            {
                return mid;
            }
            else
            {
                high = mid - 1;
            }
        }
        else
        {
            low = mid   1;
        }
    }
    return -1; 
}

The checkArr(HypotheticalBool[] arr, int elementIndex) is the CPU hungry method I mentioned above. In the worst case, it takes this code 11 calls to checkArr() to find the correct element.

What I am trying to do is bring that number down. Is there a more efficient implementation of binary search to achieve this goal?

CodePudding user response：

While trying to run your algorithm I got an IndexOutOfRangeException. I had to change the second if-statement to if (mid < 1 || !CheckArr(arr, mid - 1)).

To simplify things I worked with a real Boolean array and added a counter to the array checking method. Then I repeated the search by filling the array with 0 up to 50 false values and the rest with true values. The mean number of counts for your FindFirstTrue method was 7.68 with counts in the range of 2 .. 11 (inclusive).

This can be improved, as you are calling checkArr twice. This is my implementation:

static int FindFirstTrue(bool[] arr)
{
    int low = 0;
    int high = arr.Length - 1;
    int mid = 0;
    bool lastCheck = false;
    while (low <= high) {
        mid = (low   high) / 2;
        lastCheck = CheckArr(arr, mid);
        if (lastCheck) {
            high = mid - 1;
        } else {
            low = mid   1;
        }
    }
    if (!lastCheck) {
        mid  ;
    }
    return low < arr.Length ? mid : -1;
}

The mean number of counts is 5.86 with counts in the range of 5 .. 6 (inclusive). This is 23.7% less.

The theoretical number of counts for a binary search is log₂(50) ≈ 5.64. So, 5.86 is pretty close to the optimum.

But depending on the nature of your real array, this could be improved. E.g., if you have a range of numbers who approximate a known function then the problem could be transformed into root search problem. There are better algorithms for this kind of problem than binary search. See also Root-finding algorithms