Prolem with binary search algorithm

Question

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

The basic principle behind a binary search is that the input array has to be sorted. You missed that part. — Debosmit Ray
– Debosmit Ray, Commented Mar 15, 2016 at 3:38

Debosmit Ray · Accepted Answer · 2016-03-15 03:39:21Z

1

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.

answered Mar 15, 2016 at 3:39

Debosmit Ray

5,4332 gold badges31 silver badges44 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Pisces Over a year ago

Thanks! I know,the BinarySearch Algorithm should in a sorted array! I am a newbie in algorithm, thank you very much!@Debosmit Ray

Debosmit Ray Over a year ago

@Pisces Sure thing. It would be nice, if you could accept an answer if your issue is resolved. From here, "Accepting an answer is important as it both rewards posters for solving your problem and informs others that your issue is resolved."

MikeCAT · Accepted Answer · 2016-03-15 03:37:15Z

1

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));

}

answered Mar 15, 2016 at 3:37

MikeCAT

75.1k11 gold badges50 silver badges71 bronze badges

1 Comment

VolkerK Over a year ago

You're right. But the example code the OP has linked to also uses Arrays.sort(whitelist);. So, it seems permissible to use the built-in method for this ...homework(?)

Collectives™ on Stack Overflow

Prolem with binary search algorithm

2 Answers 2

2 Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related