Algorithms Searching suggest change

Binary Search On Sorted Numbers

It’s easiest to show a binary search on numbers using pseudo-code

int array[1000] = { sorted list of numbers };
int N = 100;  // number of entries in search space;
int high, low, mid; // our temporaries
int x; // value to search for

low = 0;
high = N -1;
while(low < high)
{
    mid = (low + high)/2;
    if(array[mid] < x)
        low = mid + 1;
    else
        high = mid;  
}  
if(array[low] == x)
    // found, index is low
else
    // not found

Do not attempt to return early by comparing array[mid] to x for equality. The extra comparison can only slow the code down. Note you need to add one to low to avoid becoming trapped by integer division always rounding down.

Interestingly, the above version of binary search allows you to find the smallest occurrence of x in the array. If the array contains duplicates of x, the algorithm can be modified slightly in order for it to return the largest occurrence of x by simply adding to the if conditional:

while(low < high)
    {
        mid = low + ((high - low) / 2);
        if(array[mid] < x || (array[mid] == x && array[mid + 1] == x))
            low = mid + 1;
        else
            high = mid;  
    }

Note that instead of doing mid = (low + high) / 2, it may also be a good idea to try mid = low + ((high - low) / 2) for implementations such as Java implementations to lower the risk of getting an overflow for really large inputs.

Feedback about page:

Feedback:
Optional: your email if you want me to get back to you:



Table Of Contents