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

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

大致题意：
统计一个数字在排序后（升序）数组中出现的次数。

思路

二分查找

排序后的数组，查找元素肯定是二分。
既然找次数，那就改变二分的优先级。

• 对比时先判断当前位置元素是否大于等于目标，优先查找左半段，这样就会先找到目标出现的最左位置
• 对比时先判断当前位置元素是否小于等于目标，优先查找右半段，这样就会先找到目标出现的最右位置

然后，加上特判。

• 找到的最左位置元素是否为目标？若否代表数组无该元素，返回0
• 最左位置是否为数组末尾位置？若是则返回1
• 找到最左位置后，末尾元素是否为目标？若是直接返回末尾减去最左位置

之后就是返回右减左，即为次数

代码：

public int search(int[] nums, int target) {
        
        if (nums.length == 0) 
            return 0;
        else if (nums.length == 1)
            return target == nums[0] ? 1 : 0;
        else if (nums[nums.length - 1] == target && nums[0] == target) // 所有元素都为目标
            return nums.length;
        else {
            int left = binarySearch(nums, target);
            if (nums[left] != target) // 判断找到的最左位置元素是否为目标
                return 0;
            else {
                if (left == nums.length-1) { // 判断找到的最左位置是否为末尾
                    return 1;
                }
                else if (nums[nums.length-1] == target) // 判断找到最左位置后，末尾元素是否为目标
                    return nums.length - left;
                else {
                    int right = binarySearchRight(nums, left, target);
                    return right - left;
                }
                    
            }
            
        }
    }

    public int binarySearch(int[] nums, int target) {
        int low = 0;
        int high = nums.length - 1;
        while (low < high) {
            int mid = (low + high) / 2;
            if (target <= nums[mid]) // 优先查找左半段
                high = mid;
            else
                low = mid + 1;
        }
        return low;
    }
    public int binarySearchRight(int[] nums, int begin, int target) {
        int low = begin;
        int high = nums.length - 1;
        while (low < high) {
            
            int mid = (low + high) / 2;
            if (target >= nums[mid]) { // 优先右半段
                low = mid + 1; // 找到目标，low++，那么最后返回的就会是最右位置+1
            }
            else
                high = mid;
        }
        return low; // 其实返回的是最右位置+1
    }

有趣的是，可以看出两个函数除了中间的if语句不同，其他相同，所以可用标记将其整合，如题解所示：

public int binarySearch(int[] nums, int target, boolean lower) { 
		// 若lower为true，那么即使用左半段if语句
        int left = 0, right = nums.length - 1, ans = nums.length;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] > target || (lower && nums[mid] >= target)) {
                right = mid - 1;
                ans = mid; // 该ans可以不要，low也可
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }