704.二分查找

class Solution {
public:
    int search(vector<int>& nums, int target)
    {
        if (nums.empty()) return -1;
        return  binarySearch(0, (nums.size() - 1) / 2, nums.size() - 1, nums, target);
    }
    int binarySearch(int begin, int mid, int end, vector<int>& nums, int target)
    {
        //结束条件：当前只剩一个元素并且不符合查找值
        if (begin>end)
        {
            return -1;
        }
        //当前中间值为要查找值
        if (nums[mid] == target)
            return mid;
        if (nums[mid]>target&&binarySearch(begin, (begin + mid - 1) / 2, mid - 1, nums, target)>=0)
        {
            return binarySearch(begin, (begin + mid - 1) / 2, mid - 1, nums, target);
        }
        else if(nums[mid]<target&&binarySearch(mid + 1, (mid + end + 1) / 2, end, nums, target)>=0)
        {
            return binarySearch(mid + 1, (mid + end + 1) / 2, end, nums, target);
        }
        return -1;
    }
};

class Solution {
public:
    int search(vector<int>& nums, int target)
    {
        if (nums.empty()) return -1;
        int begin = 0;
        int end = nums.size() - 1;
        int mid;
        while (begin <= end)
        {
           mid = (begin + end) / 2;
            if (nums[mid] > target)
                end = mid - 1;
            if (nums[mid] < target)
                begin = mid + 1;
            if (nums[mid] == target)
                return mid;
        }
        return -1;
    }
};