Introduction

Binary search targets to solve such a problem

<aside> 💡 Given a sorted array arr, return the index of target value if it is contained in the array; otherwise, -1

</aside>

This will be covered in the Basic part.

In advanced part, we will cover some more variant of binary search.

Basic

Definition

Basic就是说，在一个sorted array nums里找到值为 target的 index，不然就 return -1. 如果有多个与 target相等的element，return的是哪个index是不确定的

Code Template

import java.util.Arrays;

public final class BasicSolution {

  private BasicSolution() {
  }

  public static int equalTo(final int[] nums, final int target) {
    if (nums == null) {
      throw new NullPointerException();
    }
    if (nums.length == 0) {
      throw new IllegalArgumentException("The length of nums cannot be zero.");
    }
    int left = 0, right = nums.length - 1; // left and right always inclusive
    while (left <= right) {
      final int mid = (right - left) / 2 + left;
      if (nums[mid] == target) {
        return mid; // return index here
      } else if (nums[mid] < target) {
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }
    throw new IllegalStateException("Cannot find the target value = " + target + " in array = " + Arrays.toString(nums));
  }
}

<aside> 💡 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.

</aside>

Advance I

Definition

在 Advance I 中，我们来解决 Leetcode 34. Find First and Last Position of Element in Sorted Array，即如何在sorted array中找到第一个或者最后一个满足特定条件的element的index

• 举个几个例子

Solution

我们可以用holding invariants的方法来写（这也是我大部分的解法都不需要额外的思考就能保证其正确性的方法）。invariant可以认为是code执行过程中，一定能够保证的条件。以binary search为例，如果我们能够保证每次iteration后，能够满足以下invariant，则可以保证我们得到正确的答案：

1. 符合条件的值如果存在的话，一定在left和right之间
2. 每次iteration,[left, right] 都需要被缩小