int[] enter = {1, 4, 2, 3};
int[] leave = {2, 1, 3, 4};

for(int i=1; i<=enter.length; i  ) {

  int enterNum = Arrays.binarySearch(enter, i);
  int leaveNum = Arrays.binarySearch(leave, i);

  System.out.println(i);
  System.out.println(enterNum);
  System.out.println(leaveNum);
  System.out.println("--------");
}

console returns

console

Do you know why it returns negative value?

enter & leave arrays have int value 2, 3.

As far as I know binarySeach() method returns negative when arrays don't have the key.

Am I wrong?

please help me.

CodePudding user response：

binary search returns arbitrary and generally wrong results if you give it garbage. Which you are doing here. Specifically, binary search requires that the input is sorted. Your inputs aren't sorted, thus, wrong answers come out.

Think of how you find a person in a phone book. Let's say you're trying to find jxun in the book. You open the book to exactly half, and look at the name you find there: Leslie. That's 'more' than jxun, so you take the bottom half of the phone book and get rid of it entirely. Boom, half the phone book eliminated.

Now you again look at the halfway point of what you have left: Hendriks.

So, you tear the top half of the book off and boom, again got rid of half of what was left (so now there's only 25% of the original phone book left), in only 2 steps.

Every step you get rid of half of what's left. That means that even if the book contains every soul on the planet - 7 billion entries, this 'algorithm' gets you your answer in only 33 steps! LOG2(7,000,000,000) is about 33.

Of course, this only works because the phone book is sorted. If the phone book isn't sorted, it takes about 7 billion steps to check if somebody is in that phone book, instead of 33. Other than sorting the book and then using binary search, there is no shortcut if all you get is a pile of 7 billion arbitrarily ordered folks in there.

CodePudding user response：

The pre-condition to apply binary search :

1. The given array should be sorted.

2. Middle element should be directly accessible

   for example: if given array is arr[] and first index is start and last index is end then mid index will be (start end)/2 and the middle element is directly access by arr[mid]

And the given array list are not sorted, you can apply linear search here:

int[] enter = {1, 4, 2, 3};
int[] leave = {2, 1, 3, 4};

But to apply binary search on the above array list, it must be sorted:

int[] enter = {1, 2, 3, 4};
int[] leave = {1, 2, 3, 4};