CODEWITHSUNDEEP
javabinary-search
The_Architect
The_Architect

Reputation: 1

What's wrong with my binary search?

I've just started learning Java (this is my first time programming in it). Where the print statement is (purely for test purposes), the code outputs the mid repeatedly without ever changing it. I've thought about it for several hours and cannot figure it out. Help would be greatly appreciated. 

/*class containing binary search algorithm*/
public class BinarySearch {
    /*conducts a binary search as specified by user*/
    public static int binarySearch(int queryValue, int[] list) {
    int length = list.length; 
    /*last point of list*/
    int top = length-1;       
    /*first point of list*/
    int bottom = 0;    
    /*starting midpoint of list*/
    int mid = (int)Math.round((top + bottom)/2);
    /*binary search*/
    while(bottom < top) {
        if((int)queryValue == (int)list[mid]) {
        return mid;
        }
        else if(queryValue > list[mid]) {
         bottom = mid;
         mid = (int)Math.round((top + bottom) / 2);
         StdOut.print(mid);
        }
        else {
         top = mid;
         mid = (top + bottom) / 2;
         }
    }
    /*returns -1 if user value not found*/
    return -1;
    }
}

Upvotes: 0

Views: 784

Answers (3)

The_Architect
The_Architect

Reputation: 1

public static int binarySearch(int queryValue, int[] list) {
    int length = list.length;
    /*last point of list*/
    int top = length-1;
    /*first point of list*/
    int bottom = 0;
    /*starting midpoint of list*/
    int mid = (int)Math.round((top + bottom)/2.0);
    /*binary search*/
    do {
        if (queryValue > list[mid]) {
            bottom = mid;
            mid = (int)Math.ceil((top + bottom) / 2.0);
            System.out.println(mid);
        } else {
            top = mid;
            mid = (int)Math.floor((top + bottom) / 2.0);
            System.out.println(mid);
        }
        if(queryValue == list[mid]) {
            return mid;
        }
    } while (mid < top || mid > bottom);
    /*returns -1 if user value not found*/
    return -1;
}

Upvotes: 0

Yuriy Chulovskyy
Yuriy Chulovskyy

Reputation: 163

It would be better if you provide data that you use for testing.
As for now, I see that for the following input it will hang:
binarySearch(9, new int[] {1,2,3,4,5,6,7,8,9})
mid will be 7
It's because (7+8)/2 = 7 because you work with int
Try to replace:
mid = (int)Math.round((top + bottom) / 2);
with
mid = (int)Math.round((top + bottom) / 2.0);
It will resolve the issue.
Good luck!
Updated the code to take into account edge cases:

public static int binarySearch(int queryValue, int[] list) {
    int length = list.length;
    /*last point of list*/
    int top = length-1;
    /*first point of list*/
    int bottom = 0;
    /*starting midpoint of list*/
    int mid = (int)Math.round((top + bottom)/2.0);
    /*binary search*/
    do {
        if (queryValue > list[mid]) {
            bottom = mid;
            mid = (int)Math.ceil((top + bottom) / 2.0);
            System.out.println(mid);
        } else {
            top = mid;
            mid = (int)Math.floor((top + bottom) / 2.0);
            System.out.println(mid);
        }
        if(queryValue == list[mid]) {
            return mid;
        }
    } while (mid < top && mid > bottom);
    /*returns -1 if user value not found*/
    return -1;
}

Upvotes: 0

rgettman
rgettman

Reputation: 178253

If your value is greater than the midpoint, then the midpoint is eliminated. Advance bottom one past the current mid:

bottom = mid + 1;

Similarly for the less than the midpoint case, advance top one before the current mid:

top = mid - 1;

Otherwise, you may get a case where bottom and top never cross each other.

Also, binary search works only when the input is already sorted. Please confirm/ensure that your array is already sorted.

Upvotes: 3

Related Questions