剑指Offer刷题记录，第四题。

方法一：二分+递归

思路：其实从题干描述就知道肯定会使用二分查找，最大的问题在于怎么根据题目要求调整二分查找，可以看出如下关系式(二分最难莫过于边界条件的控制)：

class Solution {
   
    int count = 0;
    public int search(int[] nums, int target) {
   
        // 特例
        if (nums == null || nums.length == 0 || target < nums[0] || target > nums[nums.length - 1]) {
   
            return 0;
        }
        binarySearch(nums, target, 0, nums.length - 1);
        return count;
    }
    public void binarySearch(int[] nums, int target, int left, int right) {
   
        if (left <= right) {
   
            int mid = left + (right-left) / 2;
            if (nums[mid] > target) {
   
                binarySearch(nums, target, left, mid - 1);
            }else if (nums[mid] < target) {
   
                binarySearch(nums, target, mid + 1, right);
            }else {
   
                count += 1;
                binarySearch(nums, target, left, mid - 1);
                binarySearch(nums, target, mid + 1, right);
            }
        }
    }
}

时间复杂度：O(LogN), N为数组长度，二分查找时间复杂度为O(LogN)，但当数组中全是target值时，整体复杂度退变成O(N)。
空间复杂度：O(1), 未使用额外空间。