395
分类：
Code
简介：考研时需要学习的一个算法，这里手打实现一个简单的折半查找折半查找（二分查找）介绍折半查找法是效率较高的一种查找方法。假设有已经按照从小到大的顺序排列好的五个整数a0~a4，要查找的数是X，其基本思想是： 设查找数据的范围下限为l=0，上限为h=4，求中点m=（l+h）/2，用X与中点元素am比较，若X等于am，即找到，停止查找；否则，若X大于am，替换下限l=m+1，到下半段继续查找；若X小于am，换上限h=m 1，到上半段继续查找；如此重复前面的过程直到找到或者l>h为止。如果l>h，说明没有此数，打印找不到信息，程序结束。 。实现递归#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int a[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
//vector<int> array;
int BineraySearch(int* a,int left,int right,int target)//返回所在下标
{
if(left>right)
return 1;
int mid = (right left) / 2 + left;
cout<<left<<" "<<mid<<" "<<right<<endl;
if(a[mid]<target)
{
left = mid + 1;
}
else if(a[mid]>target)
{
right = mid 1;
}
else
{
return mid;
}
BineraySearch(a,left,right,target);
}
int main()
{
int target=0;
cin >> target;
cout<<BineraySearch(a,1,10,target);
return 0;
}
非递归#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int a[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int main()
{
int target=0;
cin >> target;
// cout<<BineraySearch(a,1,10,target);
int left=0;
int right=9;
while(left<=right)
{
int mid = (right left) / 2 + left;
cout<<left<<" "<<mid<<" "<<right<<endl;
if(a[mid]<target)
{
left = mid + 1;
}
else if(a[mid]>target)
{
right = mid 1;
}
else
{
cout<<mid<<endl;
break;
}
}
if(left>right)
cout<<"Failed"!<<endl;
return 0;
}
