Java Arrays binarySearch

Question

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?

Oliver Charlesworth · Accepted Answer · 2012-05-07 20:28:21Z

8

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

answered May 7, 2012 at 20:28

Oliver Charlesworth

274k34 gold badges591 silver badges687 bronze badges

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

1 Comment

Louis Wasserman Over a year ago

Instead, it means "could be anything, we're not specifying what it is." It could be different on Tuesdays, or if it's sunny outside, or how your mother is feeling today: it's not specified.

Nayuki · Accepted Answer · 2022-05-11 17:26:15Z

6

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.

edited May 11, 2022 at 17:26

answered May 7, 2012 at 20:30

Nayuki

18.8k6 gold badges61 silver badges84 bronze badges

Comments

esej · Accepted Answer · 2012-05-07 20:28:12Z

4

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.

answered May 7, 2012 at 20:28

esej

3,0571 gold badge20 silver badges22 bronze badges

Comments

user1181445 · Accepted Answer · 2012-05-07 20:28:33Z

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

gabitzish · Accepted Answer · 2012-05-07 20:32:08Z

3

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

answered May 7, 2012 at 20:32

gabitzish

9,7117 gold badges47 silver badges67 bronze badges

Comments

Victor Sorokin · Accepted Answer · 2012-05-07 20:28:51Z

1

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

answered May 7, 2012 at 20:28

Victor Sorokin

12k2 gold badges38 silver badges53 bronze badges

1 Comment

Nayuki Over a year ago

In other words, the array size was changed from 5 to 6.

Collectives™ on Stack Overflow

Java Arrays binarySearch

6 Answers 6

1 Comment

Comments

Comments

Comments

Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

6 Answers 6

1 Comment

Comments

Comments

Comments

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related