[剑指offer]面试题第[53-1]题[JAVA][在排序数组中查找数字-1][二分法][暴力法]

【问题描述】[中等]

统计一个数字在排序数组中出现的次数。 示例 1: 输入: nums = [5,7,7,8,8,10], target = 8 输出: 2 示例 2: 输入: nums = [5,7,7,8,8,10], target = 6 输出: 0

【解答思路】

1. 暴力法/遍历

时间复杂度：O(N) 空间复杂度：O(1)

public int search(int[] nums, int target) { int count = 0; for(int num : nums){ if(num == target){ count++; } } return count; }

2. 二分法

有序数组 分别找到 taret 的左右边界 right - left +1 时间复杂度：O(logN) 空间复杂度：O(1)

public class Solution { public int search(int[] nums, int target) { int len = nums.length; if (len == 0) { return 0; } int firstPosition = findFirstPosition(nums, target); if (firstPosition == -1) { return 0; } int lastPosition = findLastPosition(nums, target); return lastPosition - firstPosition + 1; } private int findFirstPosition(int[] nums, int target) { int len = nums.length; int left = 0; int right = len - 1; while (left < right) { int mid = left + (right - left) / 2; // 注意这样写，可以从左边收缩待搜索区间的范围，进而找到第一次出现的位置 if (nums[mid] < target) { // mid 以及 mid 左边都不是，下一轮搜索区间在 [mid + 1, right] left = mid + 1; } else { right = mid; } } if (nums[left] == target) { return left; } return -1; } private int findLastPosition(int[] nums, int target) { int len = nums.length; int left = 0; int right = len - 1; while (left < right) { int mid = left + (right - left + 1) / 2; // 注意这样写，可以从右边收缩待搜索区间的范围，进而找到最后一次出现的位置 if (nums[mid] > target) { // mid 以及 mid 右边都不是，下一轮搜索区间在 [left, mid - 1] right = mid - 1; } else { left = mid; } } return left; } }

【总结】

1.二分查找思路

2.排除法思考二分法

1、确定搜索区间初始化时候的左右边界，有时需要关注一下边界值。在初始化时，有时把搜索区间设置大一点没有关系，但是如果恰好把边界值排除在外，再怎么搜索都得不到结果。

2、无条件写上 while (left < right) ，表示退出循环的条件是 left == right，对于返回左右边界就不用思考了，因此此时它们的值相等；

3、先写下取整的中间数取法，然后从如何把 mid 排除掉的角度思考 if 和 else 语句应该怎样写。

（这里建议写两个注释。）

一般而言，我都会把**“什么时候不是目标元素”**作为注释写在代码中，提醒自己要判断正确，这一步判断非常关键，直接影响到后面的代码逻辑。然后接着思考 mid 不是解的情况下，mid 的左右两边可能存在解，把下一轮搜索的区间范围作为注释写进代码里，进而在确定下一轮搜索区间边界的收缩行为时，不容易出错。

if 有把握写对的情况下，else 就是 if 的反面，可以不用思考，直接写出来。

** 说明：这种思考方式，就正正好把待搜索区间从逻辑上分成两个区间，一个区间不可能存在目标元素，进而在另一个区间里继续搜索，更符合“二分”的语义。**

4、根据 if else 里面写的情况，看看是否需要修改中间数下取整的行为。 上面已经说了，只有看到 left = mid 的时候，才需要调整成为上取整，记住这一点即可，我因为刚开始不理解这种写法，遇到很多次死循环，现在已经牢记在心了。

5、退出循环的时候，一定有 left == right 成立。有些时候可以直接返回 left （或者 right，由于它们相等，后面都省略括弧）或者与 left 相关的数值，有些时候还须要再做一次判断，判断 left 与 right 是否是我们需要查找的元素，这一步叫“后处理”。

// 有可能区间内不存在目标元素，因此还需做一次判断 if (nums[left] == target) { return left; } return -1; public int searchInsert(int[] nums, int target) { int len = nums.length; if (len == 0) { return 0; } int left = 0; // 因为有可能数组的最后一个元素的位置的下一个是我们要找的，故右边界是 len int right = len; while (left < right) { int mid = (left + right) >>> 1; // 小于 target 的元素一定不是解 if (nums[mid] < target) { // 下一轮搜索的区间是 [mid + 1, right] left = mid + 1; } else { right = mid; } } return left; }

转载链接：https://leetcode-cn.com/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof/solution/er-fen-cha-zhao-fa-zhao-dao-di-yi-ci-chu-xian-de-w/