CODEWITHSUNDEEP
javaarraysbinary-search
ab_dev86
ab_dev86

Reputation: 1982

Java Arrays binarySearch

Here is my simple piece of code, where I build a String array and try to search a string within this array:

String[] arr = new String[5];
arr[0] = "ccc";
arr[1] = "aaa";
arr[2] = "bbb";
arr[3] = "eee";
arr[4] = "ddd";

System.out.println(Arrays.binarySearch(arr,"eee"));

Taken directly from Java 6 binarySearch documentation:

The array must be sorted prior to making this call. If it is not sorted, the results are undefined

Actually, I ran my code several time getting as output always 3 which is the position of eee in my not sorted array, but the result seems not to be "undefined" as the documentation said.

What am I missing?

Upvotes: 2

Views: 3092

Answers (6)

Nayuki
Nayuki

Reputation: 18533

When we're talking about how a piece of code will behave, the term "undefined" means that the program execution could do any of these things:

  • Return the wrong answer
  • Loop forever
  • Crash immediately
  • Corrupt some data and cause a crash much later
  • Do something else unintended (e.g. erase your hard drive)
  • Be lucky and return the right answer

As advice for the programmer, don't invoke undefined behaviour, because anything can happen, good or bad, now or later.

In your case, you tested searching for "eee" and it happens to produce the correct result.

Now try searching for "ccc", what happens? Try searching for "aaa". Try searching for "bbb". Try searching for "ddd". I'll bet that some of these searches will return "not found" even though the value is clearly in the array.

Upvotes: 6

gabitzish
gabitzish

Reputation: 9691

"Undefined" means that the algorithm will run on your array, but the result is not guaranteed to be correct (binary search strongly needs a sorted array in order to work). Your example works because this is what happens:

  • enter binary search with first = 0, last = 4, middle = 2 compare
  • array[middle] with "eee" ("bbb"<"eee") => first = 2 + 1; middle = 3;
  • compare array[middle] with "eee" => "found" ; return 3;

Upvotes: 3

Victor Sorokin
Victor Sorokin

Reputation: 11996

Adding to esej's answer, here's modification of your program which returns wrong answer:

public class Main {
    public static void main(String[] args) {
        String[] arr = new String[6];
        arr[0] = "ccc";
        arr[1] = "aaa";
        arr[2] = "bbb";
        arr[3] = "eee";
        arr[4] = "ddd";
        arr[5] = "aaa";

        System.out.println(Arrays.binarySearch(arr, "eee"));
    }
}

Upvotes: 1

user1181445
user1181445

Reputation:

Binary search as defined by many institutes, books, professors... etc. Required the elements to be sorted in either an alphabetical or a numerical way.

import java.util.Arrays;

public class Main {
  public static void main(String[] args) {
    String[] arr = new String[6];
    arr[0] = "ccc";
    arr[1] = "aaa";
    arr[2] = "bbb";
    arr[3] = "eee";
    arr[4] = "ddd";
    arr[5] = "aaa";
    System.out.println(Arrays.toString(arr));
    System.out.println("\"eee\" was found at index: " + Arrays.binarySearch(arr, "eee"));
    Arrays.sort(arr);
    System.out.println(Arrays.toString(arr));
    System.out.println("\"eee\" was found at index: " + Arrays.binarySearch(arr, "eee"));
  }
}

Upvotes: 4

Oliver Charlesworth
Oliver Charlesworth

Reputation: 272457

"Undefined" does not mean "will definitely give you the wrong result", or "will definitely crash".

Upvotes: 8

esej
esej

Reputation: 3059

You are missing that "the results are undefined" includes the possibility of a "correct" answer, as in this case.

If you change arr[1] to "eee" you'll see a different result.

Upvotes: 4

Related Questions