Binary search does not work. Wrong "first" and "last"

user_13394732 0
Viewed 54
public class Programma {

    public static void main(String args[]) {
        int array[] = { 1, 2, 4, 5, 6, 7, 8 };
        int v = 4;
        int first = 0;
        int last = 6;
        if (binary_search(array, v, first, last) == 1) {
            System.out.println("Value " + v + " found!");
        } else {
            System.out.println("Value " + v + " not found.");
        }
    }

    static int binary_search(int array[], int v, int first, int last) {
        if (first > last) {
            return 0;
        }
        int m = (first + last) / 2;
        System.out.println("Actual m is: " + m + " of " + first + last);
        if (array[m] == v) {
            return 1;
        } else if (v > array[m]) {
            binary_search(array, v, m + 1, last);
        } else {
            binary_search(array, v, first, m - 1);
        }
        return -1;
    }
}

Output is:

Actual m is: 3 of 06
Actual m is: 1 of 02
Actual m is: 2 of 22
Value 4 not found.

I really don't understand why the first and the last become from 06 to 02, when they should become 46, since 3 is smaller than 4.... I added the condition if (v>array[m]) that should do the work but it actually doesn't.

binary-search java
2 Answers

You forget to retrive result of binary_search:

if (array[m] == v)
    return 1;
if (v > array[m])
    return binary_search(array, v, m + 1, last);
return binary_search(array, v, first, m - 1);

I think you can simplify your code and select primary binary_search mathod to accept an array and required value:

public static void main(String... args) {
    int[] arr = { 1, 2, 4, 5, 6, 7, 8 };
    int val = 4;
    int pos = binarySearch(arr, val);

    if (pos == -1)
        System.out.format("Value %s was not found.\n", val);
    else
        System.out.format("Value %d was found at position %d\n", val, pos);
}

public static int binarySearch(int[] arr, int val) {
    return binarySearch(arr, val, 0, arr.length - 1);
}

private static int binarySearch(int[] arr, int val, int left, int right) {
    while (left <= right) {
        int mid = (left + right) / 2;

        if (arr[mid] == val)
            return mid;
        if (arr[mid] < val)
            left = mid + 1;
        else if (arr[mid] > val)
            right = mid - 1;
    }

    return -1;
}
user_34613970

You can use the method created for it if you are looking for a solution and not for studies purpose.

    import java.util.Arrays;
    public static void main(String[] args) 
    { 
        int intArr[] = {10,20,15,22,35};
        int intKey = 22;
        Arrays.sort(intArr); 
        System.out.println(intKey + " found at index = " + Arrays.binarySearch(intArr,intKey));
    }
user_62274930
Related