题目描述
给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1。
算法1
循环式的二分查找
C++ 代码
int binarySearch(vector<int>& nums,int target)
{
int nLeft=0,nRight=nums.size()-1;
int nMid;
// 采用循环实现二分,不会造成递归的开销
while(nLeft<=nRight)
{
nMid=nLeft+((nRight-nLeft)>>1);
if(nums[nMid]==target) return nMid;
else if(nums[nMid]<target) nLeft=nMid+1;
else nRight=nMid-1;
}
return -1; // 未找到返回-1
}
int search(vector<int>& nums, int target) {
return binarySearch(nums, 0, nums.size() - 1, target);
}
算法2
递归式的二分查找
C++ 代码
int binarySearch(vector<int>& nums, int nLeft, int nRight, int target) {
if (nLeft > nRight)
return -1;
int nMid = nLeft + ((nRight - nLeft) >> 1);
if (nums[nMid] == target)
return nMid;
else if (nums[nMid] < target)
return binarySearch(nums, nMid + 1, nRight, target);
else
return binarySearch(nums, nLeft, nMid - 1, target);
}
int search(vector<int>& nums, int target) {
return binarySearch(nums, 0, nums.size() - 1, target);
}