Binary Search

Introduction

Binary search introduces such a problem:
Given a sorted array a, find the index of the target value. This will be covered in the Basic part; for advanced part, we will cover some more variant of binary search.

Basic

The code is extremely simple.

example of code

Several tricky things needs to be pointed out:

1. mid calculation The reason we use int mid = (right - left) / 2 + left, rather than (left + right) / 2, is that left + right will not always fall into the range of int.

Advanced

Abstraction of binary search. An easy observation is Given a monotonic function f, which returns a boolean value and an sorted array of elements, we can apply binary search to find the first_occurrence or last_occurrence that makes the f return true

Key statement:

1. [left, right] should alway contains the target index
2. Every time the [left, right] needs to be shrunk.

Code Snippet

example of code

First Occurrence

  public static int binarySearchFirstOccurrence(final int[] nums, Function<Integer, Boolean> isSatisfied,
                                                Function<Integer, Integer> allFalseErrorHandling) {
    if (nums == null) {
      throw new NullPointerException();
    }
    if (nums.length == 0) {
      return allFalseErrorHandling.apply(nums.length);
    }

    int left = 0, right = nums.length - 1;
    while (left < right) {
      int mid = (right - left) / 2 + left;
      if (isSatisfied.apply(nums[mid])) {
        right = mid;
      } else {
        left = mid + 1;
      }
    }

    // all element doesn't satisfy the condition
    if (!isSatisfied.apply(nums[left])) {
      return allFalseErrorHandling.apply(nums.length);
    }
    return left;
  }

How to decide left = mid (+ 1)

Readers might notice in some part of the code, I didn't use +1 or -1. How to decide this?

Given the function midVal -> Integer.compare(midVal, 3) >= 0), whis is to find the first element >= 3 and example above, we have the following situation to consider.

1. mid falls (-inf, 1]. First, f(mid) is still false, we are going to move left. Second, since we are looking for the first occurrence of true value, left won't be the answer, so we can do left + 1

2. mid falls (1, 3). This situation can be vary, if f(array[mid]) is false, go to situation 1; otherwise, go to situation 3.

3. mid falls [3, +inf). Apparent, we are moving right. We need to keep 3 in the range, the 3 that mid index points to might be the first ocurrence. we cannot use -1 to remove this mid

Last occurrence

public static int binarySearchLastOccurrence(final int[] nums, Function<Integer, Boolean> isSatisfied,
                                               Function<Integer, Integer> allFalseErrorHandling) {
    if (nums == null) {
      throw new NullPointerException();
    }
    if (nums.length == 0) {
      return allFalseErrorHandling.apply(nums.length);
    }

    int left = 0, right = nums.length - 1;
    while (left < right) {
      int mid = (right - left + 1) / 2 + left;
      if (isSatisfied.apply(nums[mid])) {
        left = mid;
      } else {
        right = mid - 1;
      }
    }

    // all element doesn't satisfy the condition
    if (!isSatisfied.apply(nums[left])) {
      return allFalseErrorHandling.apply(nums.length);
    }
    return left;
  }

How to decide int mid = (right - left + 1) / 2 + left;

Readers might have noticed that the mid calculation is int mid = (right - left + 1) / 2 + left;

The reason is very simple. Let's say eventually, the left right pointer are pointing to the two sides of the divide of false and true.

It will become infinite loop, since the mid always points to the so-called pre-mid if we use int mid = (right - left) / 2 + left;.</p>

The pre-mid means if the interval [left, right] size is even, it will points to the last element of the first-half; if odd, it points to the mid. For example, [0, 1, 2, 3] will point to 1; [1, 2, 3] points to 2

How to use my function to test.

See example here