整理自九章。

  • 第一境界
    • 写出不会死循环的二分法
    • 递归与非递归的权衡
  • 第二境界
    1. 在排序的数据集上进行二分
    2. 找到满足某个条件的第一个位置或者最后一个位置
  • 第三境界
    • 在未排序的数据集上进行二分
    • 保留有解的一半，或者去掉无解的一半
  • 第四境界
    • 在答案集上进行二分
    • 二分答案并验证答案偏大还是偏小

LintCode 457：经典二分查找问题

https://www.lintcode.com/problem/classical-binary-search

描述

在一个排序数组中找一个数，返回该数出现的任意位置，如果不存在，返回-1。

样例

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

解题思路

经典二分查找题目~~。

AC代码

  1. public int findPosition(int[] nums, int target) {
  2.     // 空数组直接返回-1；
  3.     if (nums.length < 1) {
  4.         return -1;
  5.     }
  7.     int start = 0, end = nums.length - 1;
  8.     while (start + 1 < end) {
  9.         int mid = start + (end - start) / 2;
  10.         if (nums[mid] == target) {
  11.             return mid;
  12.         } else if (nums[mid] < target) {
  13.             start = mid;
  14.         } else {
  15.             end = mid;
  16.         }
  17.     }
  19.     if (nums[start] == target) {
  20.         return start;
  21.     }
  22.     if (nums[end] == target) {
  23.         return end;
  24.     }
  26.     return -1;
  28. }

LintCode 460：在排序数组中找最接近的K个数

https://www.lintcode.com/problem/find-k-closest-elements

描述

给一个目标数target，一个非负整数K，一个按照升序排列的数组A。在A中找到与target最接近的K个整数。
返回这K个数并按照与target的接近程度从小到大排序，如果接近程度相当，那么小的数排在前面。

  1. k是一个非负整数，并且总是小于已排序数组的长度。
  2. 给定数组的长度是正整数, 不会超过 10^4104
  3. 数组中元素的绝对值不会超过 10^4104

    样例

    ```java 输入: A = [1, 2, 3], target = 2, k = 3 输出: [2, 1, 3]

输入: A = [1, 4, 6, 8], target = 3, k = 3 输出: [4, 1, 6]

  1. <a name="vGPI2"></a>
  2. #### 解题思路
  3. 找到最接近target的一个数，然后向两边扩展，找到k个即可。二分法 + 双指针
  4. <a name="MePcJ"></a>
  5. #### AC代码
  6. ```java
  7. public int[] kClosestNumbers(int[] A, int target, int k) {
  8.     // right为最接近target的坐标，left为right-1，从两边扩展找到K个最接近的数
  9.     int right = findUpperClosest(A, target);
  10.     int left = right - 1;
  11.     // ans保存答案
  12.     int[] ans = new int[k];
  13.     for (int i = 0; i < k; i++) {
  14.         // 左指针更靠近target则添加左指针上的数
  15.         if (isLeftClosest(A, target, left, right)) {
  16.             ans[i] = A[left--];
  17.         } else {
  18.             // 右指针更靠近target则添加右指针上的数
  19.             ans[i] = A[right++];
  20.         }
  21.     }
  22.     return ans;
  23. }
  25. // 返回左右指针谁更靠近target
  26. private boolean isLeftClosest(int[] a, int target, int left, int right) {
  27.     // 判断临界条件
  28.     if (left < 0) {
  29.         return false;
  30.     }
  31.     if (right > a.length - 1) {
  32.         return true;
  33.     }
  34.     // 判断左右指针谁更靠近target
  35.     return Math.abs(a[left] - target) <= Math.abs(a[right] - target) ? true : false;
  36. }
  38. // 找到最接近target的坐标
  39. private int findUpperClosest(int[] a, int target) {
  40.     // 就是经典二分查找
  41.     int left = 0, right = a.length - 1;
  42.     while (left + 1 < right) {
  43.         int mid = (left + right) / 2;
  44.         if (a[mid] == target) {
  45.             return mid;
  46.         } else if (a[mid] < target) {
  47.             left = mid;
  48.         } else {
  49.             right = mid;
  50.         }
  51.     }
  52.     // 返回最接近的坐标
  53.     return Math.abs(a[left] - target) <= Math.abs(a[right] - target) ? left : right;    
  54. }

LintCode 159：寻找旋转排序数组中的最小值

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

描述

假设一个排好序的数组在其某一未知点发生了旋转（比如0 1 2 4 5 6 7 可能变成4 5 6 7 0 1 2）。你需要找到其中最小的元素
你可以假设数组中不存在重复元素

样例

  1. 输入：[4, 5, 6, 7, 0, 1, 2]
  2. 输出：0
  3. 解释：
  4. 数组中的最小值为0
  6. 输入：[2,1]
  7. 输出：1
  8. 解释：
  9. 数组中的最小值为1

解题思路

根据题目可以找到旋转后数组的特点。

  • 如果这个数小于它前面的数，那它就是最小的那个，可以直接返回答案。
  • 如果它大于数组第一个元素，那么最小的元素肯定在它的右边。
  • 小于数组第一个元素，则最小的元素肯定在它的左边。

由此可不断二分找到答案。

AC代码

  1. public int findMin(int[] nums) {
  2.     // 没有旋转直接返回最小元素，也就是nums[0]
  3.     if (nums[0] < nums[nums.length - 1]) {
  4.         return nums[0];
  5.     }
  7.     int left = 0, right = nums.length - 1;
  8.     while (left + 1 < right) {
  9.         int mid = left + (right - left) / 2;
  10.         // 小于了前面的数表示就是最小数
  11.         if (nums[mid] < nums[mid - 1]) {
  12.             return nums[mid];
  13.         }
  14.         // 大于首元素，left往右移动
  15.         if (nums[mid] > nums[0]) {
  16.             left = mid;
  17.         } else if (nums[mid] < nums[nums.length - 1]) {
  18.             // 小于首元素，right往左移动
  19.             right = mid;
  20.         } 
  21.     }
  23.     return Math.min(nums[left], nums[right]);        
  24. }

LintCode 75：寻找峰值

https://www.lintcode.com/problem/find-peak-element

描述

你给出一个整数数组(size为n)，其具有以下特点：

  • 相邻位置的数字是不同的
  • A[0] < A[1] 并且 A[n - 2] > A[n - 1]

假定P是峰值的位置则满足A[P] > A[P-1]且A[P] > A[P+1]，返回数组中任意一个峰值的位置。

  • 数组保证至少存在一个峰
  • 如果数组存在多个峰，返回其中任意一个就行
  • 数组至少包含 3 个数

    样例

    ```java 输入: [1, 2, 1, 3, 4, 5, 7, 6] 输出: 1 or 6 解释: 返回峰顶元素的下标

输入: [1,2,3,4,1] 输出: 3

  1. <a name="BJLPr"></a>
  2. #### 解题思路
  3. 观察题目数据可以得知：
  5. - 位置P满足，A[P] > A[P - 1] && A[P] > A[P + 1]，那P就是峰值
  6. - 若 A[P - 1] > A[P] > A[P + 1]，又因为A[0] < A[1]，所以在0 ~ P中肯定有峰值
  7. - 若 A[P - 1] < A[P] < A[P + 1]，又因为A[n - 2] > A[n - 1]，所以在P至末尾肯定有峰值
  9. 由此可以二分查找得到答案
  10. <a name="H9cpX"></a>
  11. #### AC代码
  12. ```java
  13. public int findPeak(int[] A) {
  15.         int left = 0, right = A.length - 1;
  16.         while (left + 1 < right) {
  17.             int mid = left + (right - left) / 2;
  18.             if (A[mid] > A[mid - 1]) {
  19.                 // 满足A[P] > A[P - 1] && A[P] > A[P + 1]，即为峰值
  20.                 if (A[mid] > A[mid + 1]) {
  21.                     return mid;
  22.                 }
  23.                 // A[P - 1] < A[P] < A[P + 1],左指针右移
  24.                 left = mid;
  25.             } else {
  26.                 // 右指针左移
  27.                 right = mid;
  28.             }
  29.         }
  30.         // 返回峰值
  31.         return Math.max(A[left], A[right]);
  32. }

LintCode 183：木材加工

https://www.lintcode.com/problem/wood-cut

描述

有一些原木，现在想把这些木头切割成一些长度相同的小段木头，需要得到的小段的数目至少为 k。当然，我们希望得到的小段越长越好，你需要计算能够得到的小段木头的最大长度。
木头长度的单位是厘米。原木的长度都是正整数，我们要求切割得到的小段木头的长度也要求是整数。无法切出要求至少 k 段的,则返回 0 即可。
挑战：O(n log Len), Len为 n 段原木中最大的长度

样例

  1. 输入:
  2. L = [232, 124, 456]
  3. k = 7
  4. 输出: 114
  5. Explanation: 我们可以把它分成114cm的7段，而115cm不可以
  7. 输入:
  8. L = [1, 2, 3]
  9. k = 7
  10. 输出: 0
  11. 说明:很显然我们不能按照题目要求完成。

解题思路

题目中有提到用O(n log Len)的算法，能够实现logN的算法之一便是二分法，所以可以考虑二分。
二分枚举木头长度，从0到长度最长的木头长度，从答案验证是否能够切成K段。能够切成K段左指针右移，不能右指针左移。

AC代码

  1. public int woodCut(int[] L, int k) {
  2.     // 临界直接返回
  3.     if (L.length < 1){
  4.         return 0;
  5.     }
  6.     // 找到长度最长的木头
  7.     int maxLen = L[0];
  8.     for (int i = 1; i < L.length; i++) {
  9.         maxLen = Math.max(maxLen, L[i]);
  10.     }
  11.     // 二分枚举木头长度
  12.     int ans = 0;
  13.     int left = maxLen / k, right = maxLen;
  14.     while (left + 1< right) {
  15.         int mid = left + (right - left) / 2;
  16.         if (check(L, mid, k)) {
  17.             left = mid;
  18.         } else {
  19.             right = mid;
  20.         }
  21.     }
  22.     if (check(L, right, k)) {
  23.         return right;
  24.     }
  25.     return left;
  27. }
  29. // 判断是否能够切成K段len
  30. public boolean check(int[] L, int len, int k) {
  31.     int count = 0;
  32.     for (int length : L) {
  33.         count += length / len
  34.     }    
  35.     return count >= k ? true : false;
  36. }