033.Find K Pairs with Smallest Sums

Description

Here

Solution

其实这题很简单，就一个坑

首先，写个binary search，如下

  private static int binarySearch(final int[] nums, final int target, int left, int right) {
    while (left <= right) {
      final int mid = (right - left) / 2 + left;
      if (nums[mid] == target) {
        return mid;
      } else if (target > nums[mid]) {
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }
    return -1;
  }

这个是狠robust的写法，可以handle left > right 的情况，

然后写主方程

  private static int search(final int[] nums, final int target, int left, int right) {
    if (left > right) {
      return -1;
    }
    if (left == right) {
      return target == nums[left] ? left : -1;
    }
    final int mid = (right - left) / 2 + left;
    if (nums[mid] > nums[right]) { //TODO: 应该是nums[left] 还是right
      // left side sorted
      if (nums[left] <= target && target <= nums[mid]) {
        return binarySearch(nums, target, left, mid);
      } else {
        return search(nums, target, mid + 1, right);
      }
    } else {
      if (nums[mid] <= target && target <= nums[right]) {
        return binarySearch(nums, target, mid, right);
      } else {
        return search(nums, target, left, mid - 1);
      }
    }
  }

在todo那一行，应该是nums[mid] > nums[right]还是nums[mid] > nums[left]?

1. 首先，我们的第一个method可以处理任何情况，
2. 而第二个method不能处理left > right的关系
3. 那么当[3,1]时，如果target是1，那么我们希望剩下一个元素的时候交给binary search处理，而不是search