二分法查找元素
二分法查找元素
青木
发布于 2018-05-28 15:58:17
发布于 2018-05-28 15:58:17
基本原理
二分查找的思路很简单，我们设元素的开始和结尾的元素编号分别为first和last。 除此之外，还需要设置另外的一个元素mid。 其中mid = (first+last)/2 二分法的实现思路是，每次查找都在以当前序列的中间值为一个对比点，从而每次都会把查找范围缩小到当前序列的一半的元素中。 下面是代码实现：
//二分法查找
class Solutions2
{
public:
searchBin(const vector<int>& nums,int target)
{
int first = 0;
int last = nums.size();
int mid = 0;
while(first != last)
{
mid = (last+first)/2;
if(nums[mid] == target)
return mid;
else
{
if(target > nums[mid])
first = mid + 1;
if(target < nums[mid])
last = mid - 1;
}
}
return -1;
}
};下面是测试代码：
#include<iostream>
#include<vector>
using namespace std;
//二分法查找
class Solutions2
{
public:
searchBin(const vector<int>& nums,int target)
{
int first = 0;
int last = nums.size();
int mid = 0;
while(first != last)
{
mid = (last+first)/2;
if(nums[mid] == target)
return mid;
else
{
if(target > nums[mid])
first = mid + 1;
if(target < nums[mid])
last = mid - 1;
}
}
return -1;
}
};
//主函数
int main(void)
{
vector<int> a;
a.push_back(1);
a.push_back(1);
a.push_back(1);
a.push_back(2);
a.push_back(2);
a.push_back(3);
a.push_back(4);
a.push_back(4);
a.push_back(4);
a.push_back(4);
a.push_back(5);
cout<<"after binary search "<<endl;
Solutions2 ss;
int return_binSort = ss.searchBin(a,3);
cout <<"the result is :"<<return_binSort;
cout<<endl;
return 0;
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录