剑指Offer刷题记录，第四题。
剑指 Offer 53 - I. 在排序数组中查找数字 I（easy）
方法一：二分+递归
思路：其实从题干描述就知道肯定会使用二分查找，最大的问题在于怎么根据题目要求调整二分查找，可以看出如下关系式(二分最难莫过于边界条件的控制)：
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), 未使用额外空间。
