递归法：
代码语言：javascript复制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;
}
};
迭代法：
代码语言：javascript复制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;
}
};
