Infinite loop in binary search variant (Java)

Question

My aim is to input a key and an array, and then output the number of values in that array which are less than or equal to the key, using binary search.

This is my code:

import java.util.*;
import java.io.*;

public class search {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int key = scan.nextInt();
        int size = scan.nextInt();
        int [] array = new int [size];

        for (int i = 0;i < size ;i++ ) {
            array[i] = scan.nextInt();
        }
        Arrays.sort(array);

        System.out.println(binary(key, array));
    }

    public static int binary (int key, int [] array){
        int lo = 0;
        int hi = array.length - 1;

        while (lo < hi){
            int mid = (lo + hi) / 2;
            if (array[mid] <= key){
                lo = mid;
            }

            else {
                hi = mid - 1;
            }
        }

        return lo + 1;
    }
}

With the data key = 5, array = {2,4,6,7}, the program works fine. But the moment there are three values that are less than or equal to the key, it goes haywire. For example, key = 5, array = {2,4,5,6} produces an infinite loop. I've found the reason for this but I don't see how to get around it.

Basically the mid value keeps getting calculated as the same value. What can I do to get around this? If the code is inherently wrong, then that means the the set solution for a USACO problem was wrong.

Answer 1

The sample solution seems fine. The problem with your code is that mid = (lo + hi) / 2 rounds toward lo, which is a problem since the update cases are lo = mid and hi = mid - 1. When hi == lo + 1, in the first case, no progress is made. You should round up as the sample does: mid = (lo + hi + 1) / 2 (warning: may overflow on long arrays; check your constraints).

The sample also checks whether the first value is less than the key.

Answer 2

Your Algorithm seems fine. But i see there is a problem with assigning the value for mid.

int mid = (hi+lo)/2

think of a case where your

hi=4
mid = 3

now the new value for mid will be (3+4)/2 = 3 (integer division)

so the loop will continue running without breaking.

In this case what you can do is increment the value of mid, by checking this condition.

But more effectively its seems better check the value of mid is repeating, Then break the loop. At last check whether the value of array[hi] is the same as your array[mid]

Hope this would help..

Have a nice day.. :)

EDIT

A better Way of doing would be

Change your while loop to

while(mid<hi+1){
 }

then check for equality of the values after the loop..

OR Simply set

  mid = (mid+hi+1)/2

Answer 3

In your loop, you must make your intervals ever smaller and you must also exclude the element you've just looked at. You do that when you go left, but not when you go right.

You also miss out on intervals of length 1, because you use inclusive lower and upper bounds. Your loop condition should be lo <= hi.

Finally, you return one too many: The results should be 0 when the key is smaller than the first element and it should be the array length when it is greater than the last element.

So:

static int binary(int key, int[] array)
{
    int lo = 0;
    int hi = array.length - 1;

    while (lo <= hi) {
        int mid = (lo + hi) / 2;

        if (array[mid] <= key) {
            lo = mid + 1;
        } else {
            hi = mid - 1;
        }
    }

    return lo;
}

In my opinion, it is better to use an exclusive upper bound, as Java usually does. (For example, an array of length n has elements at indoces 0 to n - 1, the upper bound n is outside the valid range.) If nothing else, it is consitent with other Java code. So:

static int binary(int key, int[] array)
{
    int lo = 0;
    int hi = array.length;

    while (lo < hi) {
        int mid = (lo + hi) / 2;

        if (array[mid] <= key) {
            lo = mid + 1;
        } else {
            hi = mid;
        }
    }

    return lo;
}