1. 题目介绍（53. 在排序数组中查找数字）

面试题53：在排序数组中查找数字 一共分为三小题：

• 题目一：数字在排序数组中出现的次数
• 题目二：0 ~ n-1 中缺失的数字
• 题目三：数组中数值和下标相等的元素

2. 题目1：数字在排序数组中出现的次数

题目链接：https://leetcode.cn/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof/

2.1 题目介绍

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

【测试用例】：
示例 1:

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

示例2：

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

【条件约束】：

提示：

• 0 <= nums.length <= 105
• -109 <= nums[i] <= 109
• nums 是一个非递减数组
• -109 <= target <= 109

【相关题目】：

注意：本题与主站 34. 在排序数组中查找元素的第一个和最后一个位置 题目相同（仅返回值不同）。

2.2 题解 – 二分查找 – O(logn)

时间复杂度O(logn)，空间复杂度O(1)

【解题思路】：

1. 暴力枚举：我们可以遍历整个数组，找到目标值就累加，统计出目标值的总数；
2. 枚举简化：我们不遍历整个数组，而是从头开始找第一个目标值，从尾找最后一个目标值，但当目标值数量为1，且是中间元素时，时间复杂度和暴力枚举没有任何区别；
3. 二分查找：我们将找第一个目标值和最后一共目标值的过程改为二分，通过二分查找可将时间复杂度降为 O(logn)。

……
【实现策略】：
二分查找算法总是先拿数组中间的数字和 k 作比较，以查找第一个目标值 k 为例：

• 如果中间的数字比 k 大，那么 k 只有可能出现在数组的前半段，下一轮我们只在数组的前半段查找就可以了。
• 如果中间的数字比 k 小，那么 k 只有可能出现在数组的后半段，下一轮我们只在数组的后半段查找就可以了。
• 如果中间的数字和 k 相等，那么我们先判断这个数字是不是第一个 k，如果中间数字的前一个数字不是 k，那么此时中间的数字刚好就是第一个 k；如果中间数字的前一个数字也是 k，那么第一个 k 肯定在数组的前半段，下一轮我们仍然需要在数组的前半段查找；
• 同理，查找最后一个目标值 k ，也是一样的操作。

class Solution {// Soultion1：二分查找public int search(int[] nums, int target) {// 定义变量 res，用来存储最后结果int res = 0;// 判断有效数组条件if (nums.length > 0) {// 找第一个和最后一个目标值int first = binarySearchFirst(nums,0,nums.length-1,target);int last = binarySearchLast(nums,0,nums.length-1,target);// System.out.printf("first=%d, last = %d",first,last);// 找到后，计算范围if (first > -1 && last > -1) res = last - first + 1;}// 最后，返回结果return res;}// 二分找第一个出现的数字public int binarySearchFirst(int[] arr, int l, int r, int k) {// 递归终止条件if (l > r) return -1;// 找出中点int mid = l + (r-l)/2;int midData = arr[mid];// 如果找到的中点，为目标值，判断它的前一个数是否也为目标值if (midData == k) { // 不为k，找到了!if ((mid > 0 && arr[mid-1] != k) || mid == 0) return mid;// 为k，没找到，向前逼近，重新找else r = mid - 1;} // 找到的中点大于目标值，向左半边继续查找else if (midData > k) r = mid - 1;// 找到的中点小于目标值，向右半边继续查找else l = mid + 1;return binarySearchFirst(arr,l,r,k);}// 二分找最后一个出现的数字public int binarySearchLast(int[] arr, int l, int r, int k) {// 递归终止条件if (l > r) return -1;// 找出中点int mid = l + (r-l)/2;int midData = arr[mid];// 如果找到的中点，为目标值，判断它的前一个数是否也为目标值if (midData == k) { // 不为k，找到了!if ((mid < r && arr[mid+1] != k) || mid == r) return mid;// 为k，没找到，向后逼近，重新找else l = mid + 1;} // 找到的中点大于目标值，向左半边继续查找else if (midData > k) r = mid - 1;// 找到的中点小于目标值，向右半边继续查找else l = mid + 1;return binarySearchLast(arr,l,r,k);}}

3. 题目2：0 ~ n-1 中缺失的数字

题目链接：https://leetcode.cn/problems/que-shi-de-shu-zi-lcof/

3.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 <= 数组长度 <= 10000

3.2 题解 – 二分 – O(logn)

时间复杂度O(1)，空间复杂度O(n)

【解题思路】：

1. 数学计算：我们可以先用公式 n(n-1)/2 求出数字 0~n-1 的所有数字之和，记为 sn，接着求出数字中所有数字的累加和，记为 sum，此时，sn-sum 得到的差值，即为缺失的数字；
2. 二分查找：因为 0~n-1 这些数字在数组中是排序的，因此数组中开始的一些数字与它们的下标相同，我们可以将那个缺失的数字记为 m，那么这个 m 正好就是数组中第一个数值和下标不相等的下标，这个问题就可以转换为如何在排序数组中找出第一个值和下标不相等的元素。【具体实现思路可参考题目1 中 求第一个目标值的过程】

1. 数学计算法：前 n-1 项和 减去 数组累加和，所产生的差即为缺少的数字。

class Solution {// Solution1：数学计算public int missingNumber(int[] nums) {// 获取数组长度int n = nums.length + 1;// 前 n-1 项和int sn = n*(n-1)/2;// 循环遍历数组和int sum = 0;for (int i : nums) {sum += i;}// 前n-1项和 与 数组和的差，即为缺少的数字return sn - sum;}
}

2. 二分查找：在排序数组中找出第一个值和下标不相等的元素。

class Solution {// Solution2：二分查找public int missingNumber(int[] nums) {// 无效输入判断if (nums.length <= 0) return -1;// 定义左、右边界int left = 0, right = nums.length-1;// 循环二分while (left <= right) {// 获取数组中间元素int mid = left + (right - left)/2;int midData = nums[mid];// 如果当前元素和下标相同，向右继续寻找if (midData == mid) left = mid + 1;// 如果当前元素和下标不同，判断其是否为第一个不同的元素else if (midData != mid) {// 是第一个不同元素，返回当前下标if ((mid > 0 && nums[mid-1] == mid-1) || mid == left) return mid;// 不是，则向左继续寻找else right = mid-1;}}// 为测试用例[0]准备的，[0]的答案是1if (left == nums.length) return nums.length;// 循环结束，没有返回，说明输入给定数据不符合条件return -1;}
}

4. 题目3：数组中数值和下标相等的元素

题目链接：https://www.acwing.com/problem/content/65/

4.1 题目介绍

假设一个 单调递增 的数组里的每个元素都是整数并且是 唯一 的。请编程实现一个函数找出数组中任意一个 数值等于其下标 的元素。例如，在数组 [−3,−1,1,3,5] 中，数字 3 和它的下标相等。

【测试用例】：
示例1：

输入：[-3, -1, 1, 3, 5]
输出：3

【条件约束】：

提示：

• 1 <= 数组长度 <= 100
• 如果不存在，则返回-1。

4.2 题解 – 二分 – O(logn)

时间复杂度O(1)，空间复杂度O(n)

【解题思路】：

1. 暴力枚举：从头到尾依次扫描数值中的数字，并逐一检验数字是不是和下标相等；
2. 二分查找：查找数组值与下标相同的元素。

……
【实现策略】：
二分的实现策略：

• 如果 数组值和下标 相同，则直接返回下标；
• 如果 数组值和下标 不同，分两种情况讨论：
  • 数组值大于下标，由于数组是单调递增的，则说明该值右边元素值也都大于下标，可以忽略，此时我们可以去左边的值进行寻找；
  • 数组值小于下标，同理，该值左边的元素在也都小于下标，忽略，此时去右边继续寻找。

class Solution {// Solution1：二分public int getNumberSameAsIndex(int[] nums) {// 无效输入判断int n = nums.length;if (n <= 0) return -1;// 定义边界int left = 0, right = n-1;// 循环二分while (left <= right) {// 获取当前的中间元素int mid = left + (right - left)/2;int midData = nums[mid];// 判断当前数是否等于下标，如果等于，则直接返回if (midData == mid) return mid;// 如果当前数大于下标，由于单调递增，则右边的数也都大于小标，所以应往左找else if (midData > mid) right = mid-1;// 如果当前数小于下标，应往右找else left = mid+1;}// 循环结束，没找着，返回-1return -1;}
}

5. 参考资料

[1] AcWing在线活动 – 感觉还蛮有意思的