排序数组的问题首先想到的是二分法。

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

1.1 题目

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

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

示例 2:

输入: [0,1,2,3,4,5,6,7,9] 输出: 8

1.2 思路

排序数组中的搜索问题，首先想到二分法解决。
本题有两种思路：

1. 数学法：0到数组中最后一个数字正常的前n项和 - 数组中所有元素之和，差就是缺失的数字。时间复杂度为O(n)；
2. 二分查找，时间复杂度为O(lgn)。

二分查找虽然不好想，但时间复杂度优于数学法，因此面试时还是用二分查找。

1. 根据题意，数组可以按照以下规则划分为两部分，其中i为数组下标：
   1. 左子数组： nums[i] =i ；
   2. 右子数组： nums[i] != i；
2. 缺失的数字等于 “右子数组的首位元素” 对应的下标；因此考虑使用二分法查找 “右子数组的首位元素”。

while循环里的结束条件是left <= right，这个可以用以下两个例子带入来确定：[0,1,2,3,4,5,6,7,9]，[0,2,3,4,5]

1.3 代码

 class Solution {
    public int missingNumber(int[] nums) {
        int left = 0, right = nums.length - 1;
        // 跳出循环时，left 和 right 分别指向 “右子数组的首位元素” 和 “左子数组的末位元素” ，
        // 因此返回 left 即可。
        while (left <= right) {
            int mid = (left + right) >> 1;
            if (nums[mid] == mid) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }
}

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

2.1 题目

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

输入: nums = [5,7,7,8,8,10], target = 8 输出: 2

示例 2:

输入: nums = [5,7,7,8,8,10], target = 6 输出: 0

2.2 思路

排序数组查找数字，显然用二分查找，不同的是本题数组中存在重复元素，需要返回target在数组中出现的次数。

1. 常规的二分查找写法，算出mid，然后移动left和right向中间搜索；
2. 当nums[mid]== target时，说明我们找到了要找的元素，此时可以：
   1. 由mid向两边搜索，一旦搜索的元素不等于target时，向右或者向左搜索的指针就停止；
   2. 由当前left和right向mid逼近，一旦nums[left]==target或者nums[right]==target，就说明找到了target在nums数组中的边界，停止，最后通过left和right计算target数组的长度，返回个数。
3. 注意while的终止条件，当数组元素为[1], target=1时，还需要走一次while循环，因此left要==right。

   2.3 代码

   class Solution {
    public int search(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        // 当数组元素为[1], target=1时，还需要走一次while循环，因此left要==right
        while (left <= right) {
            int mid = (left + right) >> 1;
            if (nums[mid] > target) {
                right = mid - 1;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                // 让left和right都逼近mid，直到与target相等停止，最后算长度就是个数
                while (nums[left] != target) {
                    ++left;
                }
                while (nums[right] != target) {
                    --right;
                }
                return right - left + 1;
            }
        }
        return 0;
    }
   }

   3、剑指 Offer 16. 数值的整数次方

   快速幂，真难顶。

   3.1 题目

   实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，xn）。不得使用库函数，同时不需要考虑大数问题。
   示例 1：

   输入：x = 2.00000, n = 10 输出：1024.00000

示例 2：

输入：x = 2.10000, n = 3 输出：9.26100

示例 3：

输入：x = 2.00000, n = -2 输出：0.25000 解释：2-2 = 1/22 = 1/4 = 0.25

3.2 思路

二分法的应用，需要注意一点是n是负数的情况。

3.3 代码

class Solution {
    public double myPow(double x, int n) {
        return n > 0? quick(x, n): 1 / quick(x, n);
    }
    private double quick(double x, int n) {
        if (n == 0) {
            return 1.0;
        }
        double y = quick(x, n / 2);
        return (n & 1) == 0? y * y: y * y * x;
    }
}

4、704. 二分查找

4.1 题目

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
示例 1:

输入: nums = [-1,0,3,5,9,12], target = 9 输出: 4 解释: 9 出现在 nums 中并且下标为 4

示例 2:

输入: nums = [-1,0,3,5,9,12], target = 2 输出: -1 解释: 2 不存在 nums 中因此返回 -1

4.2 思路

二分查找基础版。

4.3 代码

class Solution {
    public int search(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = (left + right) >> 1;
            if (nums[mid] > target) {
                right = mid - 1;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                return mid;
            }
        }
        return -1;
    }
}