CODEWITHSUNDEEP
javaalgorithmbinary-search
Pisces
Pisces

Reputation: 41

Prolem with binary search algorithm

Recently I study algorithms,but I find a terrible problem that I cannot find the number by BinarySearch Algorithm in the link: http://algs4.cs.princeton.edu/11model/BinarySearch.java.html

public class BinaryFind {

    public static int indexOf(int[] a, int key) {
        int lo = 0;
        int hi = a.length - 1;
        while (lo <= hi) {
            // Key is in a[lo..hi] or not present.
            int mid = lo + (hi - lo) / 2;
            if (key < a[mid]) hi = mid - 1;
            else if (key > a[mid]) lo = mid + 1;
            else return mid;
        }
        return -1;
    }


    public static void main(String[] args) {
        int[] a = {1, 4, 56, 4, 3, 7, 8, 2, 66, 45};
        System.out.print(indexOf(a, 7));

    }
}

Why I cannot find the number 7?

The result:
enter image description here

Upvotes: 1

Views: 55

Answers (2)

Debosmit Ray
Debosmit Ray

Reputation: 5403

Add this line to the top of the indexOf(..) method.

Arrays.sort(a);

This will sort your input array and then you can go on with finding the index.

Upvotes: 1

MikeCAT
MikeCAT

Reputation: 75062

The array to be searched from have to be sorted to use binary search.

Try this:

public static void main(String[] args) {
    int[] a = {1, 4, 56, 4, 3, 7, 8, 2, 66, 45};

    // sort the array
    for (int i = a.length - 1; i > 0; i--) {
        for (int j = 0; j < i; j++) {
            if (a[j] > a[j + 1]) {
                int t = a[j];
                a[j] = a[j + 1];
                a[j + 1] = t;
            }
        }
    }

    System.out.print(indexOf(a, 7));

}

Upvotes: 1

Related Questions