题型 1 在数组中查找符合条件的元素的下标

说明：一般而言这个数组是有序的，也可能是半有序的，但不大可能是无序的。

35. 搜索插入位置

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
你可以假设数组中无重复元素。

思路：
使用思路2时要注意，left 要满足小于 right，因此要插入的数要插在末尾的情况要单独考虑。当 nums[mid] 严格小于目标元素时，不是解。下一轮搜索的区间为 [mid + 1, right]。

  1. class Solution {
  2.     public int searchInsert(int[] nums, int target) {
  3.         int low = 0, high = nums.length - 1, mid;
  4.         while(low <= high) {
  5.             mid = low + (high - low) / 2;
  6.             if(nums[mid] < target) {
  7.                 low = mid + 1;
  8.             } else {
  9.                 high = mid - 1;
  10.             }
  11.         }
  12.         return low;
  13.     }
  14. }
  1. class Solution {
  2.     public int searchInsert(int[] nums, int target) {
  3.         int len = nums.length;
  4.         if (len == 0) {
  5.             return 0;
  6.         }
  7.         if (nums[len - 1] < target) {
  8.             return len;
  9.         }
  11.         int left = 0, right = len - 1;
  12.         while (left < right) {
  13.             int mid = left + (right - left) / 2;
  15.             if (nums[mid] < target) {
  16.                 left = mid + 1;
  17.             } else {
  18.                 right = mid;
  19.             }
  20.         }
  22.         return left;
  23.     }
  24. }

33. 搜索旋转排序数组

假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。
你可以假设数组中不存在重复的元素。

思路：
分情况讨论，先确定 mid 和 right 的大小。如果 mid 更大，则 mid 落在了前半段。如果 target 在 left 和 mid之间，则下一轮搜索的区间为 [left, mid]。如果 target 比 left 小 或 比 mid 大，则下一轮搜索的区间为 [mid+1, right]。

  1. class Solution {
  2.     public int search(int[] nums, int target) {
  3.         int len = nums.length;
  4.         if (len == 0) {
  5.             return -1;
  6.         }
  8.         int left = 0, right = len - 1;
  9.         while (left < right) {
  10.             int mid = left + (right - left) / 2;
  12.             if (nums[mid] > nums[right]) {
  13.                 if (nums[left] <= target && target <= nums[mid]) {
  14.                     right = mid;
  15.                 } else {
  16.                     left = mid + 1;
  17.                 }
  18.             } else {
  19.                 if (nums[mid] < target && target <= nums[right]) {
  20.                     left = mid + 1;
  21.                 } else {
  22.                     right = mid;
  23.                 }
  24.             }
  25.         }
  27.         if (nums[left] == target) {
  28.             return left;
  29.         }
  31.         return -1;
  32.     }
  33. }

题型 2 在一个有上下界的区间里搜索一个整数

说明：查找一个有范围的整数。

69. x 的平方根

实现 int sqrt(int x) 函数。
计算并返回 x 的平方根，其中 x 是非负整数。
由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

思路：
要我们找的是「边界值」，这个「边界值」的特点如下：

  • 平方以后小于 x 的有可能是解；
  • 平方以后等于 x 的一定是解；
  • 平方以后大于 x 的一定不是解。

选择中间数时下取整。

  1. class Solution {
  2.     public int mySqrt(int x) {
  3.         if (x == 0) {
  4.             return 0;
  5.         }
  6.         if (x == 1) {
  7.             return 1;
  8.         }
  10.         int left = 1, right = x / 2;
  11.         while (left < right) {
  12.             int mid = left + (right - left + 1) / 2;
  14.             if (mid > x / mid) {
  15.                 right = mid - 1;
  16.             } else {
  17.                 left = mid;
  18.             }
  19.         }
  21.         return left;
  22.     }
  23. }

367. 有效的完全平方数

给定一个正整数 num，编写一个函数，如果 num 是一个完全平方数，则返回 True，否则返回 False。
说明：不要使用任何内置的库函数，如 sqrt。

  1. class Solution {
  2.     public boolean isPerfectSquare(int num) {
  3.         if (num < 2) {
  4.             return true;
  5.         }
  7.         int left = 1, right = num / 2;
  8.         while (left <= right) {
  9.             int mid = left + (right - left) / 2;
  11.             if (num % mid == 0 && num / mid == mid) {
  12.                 return true;
  13.             } else if (num / mid > mid) {
  14.                 left = mid + 1;
  15.             } else {
  16.                 right = mid - 1;
  17.             }
  18.         }
  20.         return false;
  21.     }
  22. }

题型 3 判别条件是一个函数

说明：复杂的判别函数。

练习：

4. 寻找两个正序数组的中位数

剑指 Offer

剑指 Offer 04. 二维数组中的查找

在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

思路：
从左下角开始搜索。比目标值大，则让行号 i 自减；比目标值小，则让列号 j 自增。

class Solution {
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        if (matrix.length == 0) {
            return false;
        }
        int i = matrix.length - 1, j = 0;
        while (i >= 0 && j < matrix[0].length) {
            if (matrix[i][j] == target) {
                return true;
            } else if (matrix[i][j] > target) {
                i--;
            } else {
                j++;
            }
        }
        return false;
    }
}

剑指 Offer 11. 旋转数组的最小数字

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转，该数组的最小值为 1。

思路：
二分查找。如果 mid 大于 right，则下一轮搜索区间是 [mid + 1, right]；如果 mid 等于 right，只能把 right 排除掉，下一轮搜索区间是 [left, right - 1]；如果 mid 小于 right，那么 mid 的右边一定不是最小数字，mid 有可能是，下一轮搜索区间是 [left, mid]。

class Solution {
    public int minArray(int[] numbers) {
        int len = numbers.length;
        if (len == 0) {
            return 0;
        }

        int left = 0, right = len - 1;
        while (left < right) {
            int mid = left + (right - right) / 2;
            if (numbers[mid] > numbers[right]) {
                left = mid + 1;
            } else if (numbers[mid] == numbers[right]) {
                right = right - 1;
            } else {
                right = mid;
            }
        }

        return numbers[left];
    }
}

剑指 Offer 53 - I. 在排序数组中查找数字 I

统计一个数字在排序数组中出现的次数。

思路：
二分法。
执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：42.5 MB, 在所有 Java 提交中击败了100.00%的用户

class Solution {
    public int search(int[] nums, int target) {
        if (nums == null || nums.length == 0) return 0;

        return binarySearch(nums, target + 0.5) - binarySearch(nums, target - 0.5);
    }

    private int binarySearch(int[] nums, double target) {
        int low = 0, high = nums.length - 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (nums[mid] > target) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return low;
    }
}

剑指 Offer 53 - II. 0～n-1中缺失的数字

一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。

思路：
数学。
执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：40.6 MB, 在所有 Java 提交中击败了100.00%的用户

class Solution {
    public int missingNumber(int[] nums) {
        int len = nums.length;
        int sum = (len + 1) * len / 2;
        int res = 0;
        for (int i = 0; i < len; i++) {
            res += nums[i];
        }
        return sum - res;
    }
}

思路2：
二分法。

class Solution {
    public int missingNumber(int[] nums) {
        int i = 0, j = nums.length - 1;
        while (i <= j) {
            int m = i + (j - i) / 2;
            if (nums[m] == m) {
                i = m + 1;
            } else {
                j = m - 1;
            }
        }
        return i;
    }
}