外网优秀的排序解析

Recursive Binary Search

public static int binarySearchRecursively(int[] array, int key) {
  return binarySearchRecursively(array, 0, array.length, key);
}

public static int binarySearchRecursively(
    int[] array, int fromIndex, int toIndex, int key) {
  if (toIndex <= fromIndex) return -1;

  int mid = (fromIndex + toIndex) >>> 1;
  int midVal = array[mid];

  if (key == midVal) {
    return mid;
  } else if (key < midVal) {
    return binarySearchRecursively(array, fromIndex, mid, key);
  } else {
  **加粗样式**  return binarySearchRecursively(array, mid + 1, toIndex, key);
  }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

It is important to calculate the middle position mid with an “unsigned right shift”:

int mid = (fromIndex + toIndex) >>> 1

And not as follows:

int mid = (fromIndex + toIndex) / 2

In case the sum is greater than Integer.MAX_VALUE, the second variant would lead to an overflow or a “roll over”, and the result would be a negative number.

Without the >>> operator, the following method would also be correct:

int mid = fromIndex + (toIndex - fromIndex) / 2;

Iterative Binary Search

public static int binarySearchIteratively(int[] array, int key) {
  return binarySearchIteratively(array, 0, array.length, key);
}

public static int binarySearchIteratively(
    int[] array, int fromIndex, int toIndex, int key) {
  int low = fromIndex;
  int high = toIndex;

  while (low < high) {
    int mid = (low + high) >>> 1;
    int midVal = array[mid];

    if (key == midVal) {
      return mid;
    } else if (key < midVal) {
      high = mid;
    } else {
      low = mid + 1;
    }
  }

  return -1;
}```

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

The variables low and high are not absolutely necessary here. You could also change fromIndex and toIndex within the while loop. However**, reassigning method parameters is usually considered unclean design.**

Time Complexity of Binary Search

In binary search, we halve the number of entries left to search with each search step. Or the other way around: if the number of entries doubles, we only need one more search step.

This corresponds to logarithmic effort, i.e., O(log n).

Binary Search in a LinkedList

we already iterate over n/2 elements to reach the middle in the first step of the binary search

For example, to find the position of 19, we would first have to follow the orange arrows to the center, then the blue arrows back to 23, and finally the yellow arrow to 19.

No matter if singly or doubly linked – in any case, we have to iterate over more elements than with linear search.’

When Is Binary Search in a LinkedList Useful?

Depending on the cost of the comparison function – which can be significantly higher for an object than for a primitive data type – this can make a considerable difference.