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

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

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

  1.     public int search(int[] nums, int target) {
  2.         // 搜索右边界 right
  3.         int i = 0, j = nums.length - 1;
  4.         while(i <= j) {
  5.             int m = (i + j) / 2;
  6.             if(nums[m] <= target) i = m + 1;
  7.             else j = m - 1;
  8.         }
  9.         int right = i;
  10.         // 若数组中无 target ，则提前返回
  11.         if(j >= 0 && nums[j] != target) return 0;
  12.         // 搜索左边界 right
  13.         i = 0; j = nums.length - 1;
  14.         while(i <= j) {
  15.             int m = (i + j) / 2;
  16.             if(nums[m] < target) i = m + 1;
  17.             else j = m - 1;
  18.         }
  19.         int left = j;
  20.         return right - left - 1;
  21.     }
  22. 作者：jyd
  23. 链接：https://leetcode-cn.com/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof/solution/mian-shi-ti-53-i-zai-pai-xu-shu-zu-zhong-cha-zha-5/

分析

排序数组中的搜索问题，首先想到 二分法 解决。
排序数组 nums 中的所有数字 target 形成一个窗口，记窗口的 左 / 右边界 索引分别为 left 和right ，
分别对应窗口左边 / 右边的首个元素。

本题要求统计数字 target 的出现次数，可转化为：使用二分法分别找到 左边界
left 和 右边界 right ，易得数字 target 的数量为 right−left−1 。
截屏2021-02-27 下午10.32.47.png
作者：jyd
链接：https://leetcode-cn.com/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof/solution/mian-shi-ti-53-i-zai-pai-xu-shu-zu-zhong-cha-zha-5/

优化

image.png

  1.     public int search(int[] nums, int target) {
  2.         return helper(nums, target) - helper(nums, target - 1);
  3.     }
  4.     int helper(int[] nums, int tar) {
  5.         int i = 0, j = nums.length - 1;
  6.         while(i <= j) {
  7.             int m = (i + j) / 2;
  8.             if(nums[m] <= tar) i = m + 1;
  9.             else j = m - 1;
  10.         }
  11.         return i;
  12.     }
  14. 作者：jyd
  15. 链接：https://leetcode-cn.com/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof/solution/mian-shi-ti-53-i-zai-pai-xu-shu-zu-zhong-cha-zha-5/
  16. 来源：力扣（LeetCode）
  17. 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。