3. LintCode 二分法题目（一）

LintCode 458：目标最后位置

https://www.lintcode.com/problem/last-position-of-target

描述

给一个升序数组，找到target最后一次出现的位置，如果没出现过返回-1。

样例

  1. 输入：nums = [1,2,2,4,5,5], target = 2
  2. 输出：2
  4. 输入：nums = [1,2,2,4,5,5], target = 6
  5. 输出：-1

解题思路

简单二分，只是当mid=target时，还要继续找下去。

AC代码

  1. public int lastPosition(int[] nums, int target) {
  2.     // 临界条件直接返回
  3.     if (nums == null || nums.length < 1) {
  4.         return -1;
  5.     }
  7.     int left = 0, right = nums.length - 1;
  8.     while (left + 1 < right) {
  9.         int mid = (left + right) / 2;
  10.         // 当nums[mid] == target的时候并不停止二分，left右移至mid位置继续二分查找
  11.         if (nums[mid] == target) {
  12.             left = mid;
  13.         } else if (nums[mid] < target) {
  14.             // 数字小于target，left右移
  15.             left = mid + 1;
  16.         } else {
  17.             // 数字大于target，right左移
  18.             right = mid - 1;
  19.         }
  21.     }
  22.     // right值等于target
  23.     if (nums[right] == target) {
  24.         return right;
  25.     }
  26.     // left值等于target
  27.     if (nums[left] == target) {
  28.         return left;
  29.     }
  31.     return -1;        
  32. }

LintCode 585：山脉序列中的最大值

https://www.lintcode.com/problem/maximum-number-in-mountain-sequence

描述

给 n 个整数的山脉数组，即先增后减的序列，找到山顶（最大值）
数组严格递增，严格递减

样例

  1. 输入: nums = [1, 2, 4, 8, 6, 3] 
  2. 输出: 8
  4. 输入: nums = [10, 9, 8, 7], 
  5. 输出: 10

解题思路

和前面的寻找峰值题一样一个思路。
对于位置P：

  • nums[p - 1] < nums[p] > nums[p + 1]：P点为山顶最大值
  • nums[p - 1] < nums[p] < nums[p + 1]：山顶在P点右侧
  • nums[p - 1] > nums[p] > nums[p + 1]：山顶在P点左侧

由此二分找到答案。

AC代码

  1. public int mountainSequence(int[] nums) {
  2.     // 极端情况直接判断
  3.     if (nums.length == 1 || nums[0] > nums[1]) {
  4.         return nums[0];
  5.     }
  7.     if (nums[nums.length - 1] > nums[nums.length - 2]) {
  8.         return nums[nums.length];
  9.     }
  11.     int left = 0, right = nums.length - 1;
  12.     while (left + 1 < right) {
  13.         int mid = left + (right - left) / 2;
  14.         // 找到山顶
  15.         if (nums[mid] > nums[mid + 1] && nums[mid] > nums[mid - 1]) {
  16.             return nums[mid];
  17.         }
  18.         // 山顶在右侧
  19.         if (nums[mid] > nums[mid - 1]) {
  20.             left = mid + 1;
  21.         } else {
  22.             // 山顶在左侧
  23.             right = mid - 1;
  24.         }
  25.     }
  26.     // 判断山顶
  27.     if (nums[right] > nums[right + 1] && nums[right] > nums[right - 1]) {
  28.         return nums[right];
  29.     }
  30.     if (nums[left] > nums[left + 1] && nums[left] > nums[left - 1]) {
  31.         return nums[left];
  32.     }
  33.     return 0;
  34. }

LintCode：447：在大数组中查找

https://www.lintcode.com/problem/search-in-a-big-sorted-array

描述

给一个按照升序排序的非负整数数组。这个数组很大以至于你只能通过固定的接口 ArrayReader.get(k) 来访问第k个数(或者C++里是ArrayReader->get(k))，并且你也没有办法得知这个数组有多大。
找到给出的整数target第一次出现的位置。你的算法需要在O(logk)的时间复杂度内完成，k为target第一次出现的位置的下标。
如果找不到target，返回-1。
如果你访问了一个不可访问的下标（比如越界），ArrayReader 会返回2,147,483,647

样例

  1. 输入: [1, 3, 6, 9, 21, ...], target = 3
  2. 输出: 1
  4. 输入: [1, 3, 6, 9, 21, ...], target = 4
  5. 输出: -1

挑战

O(logn)的时间复杂度，n是target第一次出现的下标。

解题思路

首先第一想法就是二分，但粗看找不到有边界，挑战也是只用logk的时间复杂度。所以思考怎么找到右边界。
将初始有边界定位1，然后不断*2，直到大于target，这所用的时间复杂度是O(logn)，满足题目要求，找到有边界后，再简单二分即可。

AC代码

  1. public int searchBigSortedArray(ArrayReader reader, int target) {
  2.     if (reader.get(0) == target) {
  3.         return 0;
  4.     }
  6.     // 寻找右边界
  7.     int right = 1;
  8.     while (reader.get(right) < target) {
  9.         right *= 2;
  10.     }
  11.     // 左边界=右边界/2
  12.     int left = right / 2;
  13.     while (left + 1 < right) {
  14.         int mid = left + (right - left) / 2;
  15.         // == target,right指针左移
  16.         if (reader.get(mid) == target) {
  17.             right = mid;
  18.         } else if (reader.get(mid) < target) {
  19.             // 小于target，left指针右移
  20.             left = mid + 1;
  21.         } else {
  22.             // 大于target，right指针右移
  23.             right = mid - 1;
  24.         }
  25.     }
  26.     if (reader.get(left) == target) {
  27.         return left;
  28.     }
  29.     if (reader.get(right) == target) {
  30.         return right;
  31.     }
  32.     // 没有答案，返回-1    
  33.     return -1;
  34. }

LintCode 62：搜索旋转排序数组

https://www.lintcode.com/problem/search-in-rotated-sorted-array

描述

假设有一个排序的按未知的旋转轴旋转的数组(比如，0 1 2 4 5 6 7 可能成为4 5 6 7 0 1 2)。给定一个目标值进行搜索，如果在数组中找到目标值返回数组中的索引位置，否则返回-1。你可以假设数组中不存在重复的元素。

样例

  1. 输入: [4, 5, 1, 2, 3] and target=1, 
  2. 输出: 2.
  4. 输入: [4, 5, 1, 2, 3] and target=0, 
  5. 输出: -1.

解题思路

解法一

前面做过查找旋转排序数组的最小值：https://www.lintcode.com/problem/find-minimum-in-rotated-sorted-array
可以先用前面的方法找到最小值，这样就把数组分成了两段有序排序的数组，在包含target的区间内在进行一次二分即可。都不包含返回-1。

解法二

第一个方法需要两次二分，还是有点繁琐。思考只用一次二分的方法。
对于位置k：

  • A[k] = targe，直接返回位置k
  • 否则要么 A[left] < A[k]，A[k] > A[right] 左半段是有序的
    • 若target在A[left]和A[k]中，就在left和k的区间中简单二分查找，右指针左移
    • 不在，左指针右移
  • 要么 A[k] < A[right]，A[k] < A[left] 右半段是有序的
    • 若target在A[k]和A[right]中，就在k和right的区间中简单二分查找，左指针右移
    • 不在，右指针左移

AC代码（解法二）

  1. public int search(int[] A, int target) {
  2.     // 边界条件
  3.     if (A.length == 0) {
  4.         return -1;
  5.     }
  7.     int left = 0, right = A.length - 1;
  8.     while (left + 1 < right) {        
  9.         int mid = left + (right - left) / 2;
  10.         // 找到target直接返回
  11.         if (A[mid] == target) {
  12.             return mid;
  13.         }
  14.         // left和mid有序上升，判断target是否在这半段
  15.         if (A[mid] > A[left]) {
  16.             if (A[left] <= target && target < A[mid]) {
  17.                 // 在这半段，右指针左移
  18.                 right = mid - 1;
  19.             } else {
  20.                 // 不在这半段，左指针右移
  21.                 left = mid + 1;
  22.             }
  23.         } else {
  24.             // mid和right区间有序上升，判断target是否在这半段
  25.             if (A[mid] < target && target <= A[right]) {
  26.                 // 在这半段，左指针右移
  27.                 left = mid + 1;
  28.             } else {
  29.                 // 不在这半段，右指针左移
  30.                 right = mid - 1;
  31.             }
  32.         }
  33.     }
  34.     if (A[left] == target) {
  35.         return left;
  36.     }
  37.     if (A[right] == target) {
  38.         return right;
  39.     }
  40.     // 没有找到返回-1
  41.     return -1;   
  42. }