C++ 输入10个数(有序),用二分法进行查找某个数是否在其中. 编写一个C++程序,在程序中输入一个长度为n的有序表,采用二...
c++\u8bed\u8a00\u4e2d\uff0c\u8f93\u5165n\u4e2a\u6570\u4ece\u5c0f\u5230\u5927\u6392\u5e8f,\u7136\u540e\u5229\u7528\u6298\u534a\u67e5\u627e,\u5728\u8fd9\u4e2a\u6709\u5e8f\u5e8f\u5217\u4e2d,\u67e5\u627e\u7528\u6237\u8f93\u5165\u7684\u67d0\u4e2a\u6574\u6570d\u3002#include
using namespace std;
void InsertSort(int A[] , int n)//\u63d2\u5165\u6392\u5e8f
{
int i,j,temp;
for(i=1;i<n;i++)
{
j=i;
temp=A[i];
while(j>0&&temp<A[j-1])
{
A[j]=A[j-1];
j--;
}
A[j]=temp;
}
}
int BinSearch(int A[] , int n, int key)//\u4e8c\u5206\u67e5\u627e
{
int mid,low,high,midValue;
low=0;
high=n-1;
while(low<=high)
{
mid=(low+high)/2;
midValue=A[mid];
if(key==midValue)
return mid;
else if(key<midValue)
high=mid-1;
else
low=mid+1;
}
return -1;
}
void main()
{
int n,i,key,j;
cout<<"\u8bf7\u8f93\u5165\u8981\u6392\u5e8f\u7684\u6570\u7684\u4e2a\u6570\uff1a";
cin>>n;
int *a=new int[n];
cout<<"\u8bf7\u8f93\u5165\u8981\u6392\u5e8f\u7684\u6570\uff1a";
for(i=0;i<n;i++)
{
cin>>a[i];
}
cout<<"\u6392\u5e8f\u540e\u7684\u6570\u4e3a\uff1a";
InsertSort(a,n);
for(i=0;i<n;i++)
{
cout<<a[i]<<" ";
}
cout<<endl;
cout<<"\u8bf7\u8f93\u5165\u8981\u67e5\u627e\u7684\u6570\uff1a";
cin>>key;
j=BinSearch(a,n,key);
if(j==-1){
cout<<"\u672a\u67e5\u5230\u4f60\u8981\u627e\u7684\u6570\uff01";
}
else{
cout<<"\u6b64\u6570\u7ec4\u4e2d\u5b58\u5728\u4f60\u8981\u67e5\u627e\u7684\u6570\u3002"<<endl;
}
}
#include
#include
const int maxn=10001;
int N;
int num[maxn];
int dat;
int main()
{
int i,j;
scanf("%d",&N);
for (i=1;i<=N;i++) scanf("%d",&num[i]);
scanf("%d",&dat);
int l=1,r=N,mid;
bool ok=false;
while (l<r && !ok)
{
mid=(l+r)/2;
if (num[mid]==dat) {ok=true; continue;}
if (num[mid]<dat) l=mid+1;
else r=mid-1;
}
mid=(l+r)/2;
if (num[mid]==dat) ok=true;
if (ok) printf("%d\n",mid);
else printf("\u67e5\u627e\u5931\u8d25\n");
system("pause");
}
#include <iostream>
using namespace std;
//a是查找的数组,二分法查找的前提条件是a数据的排序是有序的。key是待查找的变量,n是数组a的长度。
int binary( int *a, int key, int n )
{
int left = 0, right = n - 1, mid = 0;
mid = ( left + right ) / 2;
while( left < right && a[mid] != key )
{
if( a[mid] < key )
left = mid + 1;
else if( a[mid] > key )
right = mid - 1;
mid = ( left + right ) / 2;
}
if( a[mid] == key ) return mid;
return -1;
}
//调用:
//查找数组b在数组a中的下标的位置(当a中不存在b中的数据时,用-1代替)。
int main()
{
int a[10] = {1,2,3,4,5,6,7,8,9,12};
int i,b,c;
cout << "从小到大输入10个整数:";
for(i=0;i<10;i++)
cin >> a[i];
cout << "输入要查找的数:";
cin >> b;
c = binary(a,b,10);
if(c!=-1)
cout << "找到,序号:"<<c+1<<endl;
else
cout <<"没找到"<<endl;
return 0;
}
先给你一个能体现具体搜索方法的代码:
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int main()
{
int fromUser, cnt = 0;
int SOUGHT;
vector<int> range;
while(cin >> fromUser && cnt != 9)
{
range.push_back(fromUser);
++cnt;
}
cout << "You already input 10 numbers. Now decide what number to search: ";
cin >> SOUGHT;
auto BEG = range.begin(), END = range.end();
auto MID = range.begin() + (END - BEG) / 2;
while(MID != END && *MID != SOUGHT)
{
if(SOUGHT < *MID)
END = MID;
else
BEG = MID + 1;
MID = BEG + (END - BEG) / 2;
}
if(*MID == 0)
cout << SOUGHT << " NOT FOUND." << endl;
else
cout << *MID << " FOUND." << endl;
return 0;
}
实际上更推荐你使用这个方法,支持无序输入,而且代码更易懂:
#include <iostream>
#include <algorithm> // std::binary_search, std::sort
#include <vector>
using namespace std;
int main()
{
vector<int> v{1,2,3,4,5,4,3,2,1};
sort(v.begin(), v.end());
cout << "Looking for a 3 ... ";
if(binary_search(v.begin(), v.end(), 3))
cout << "FOUND!" << endl;
else
cout << "NOT FOUND." << endl;
sort(v.begin(), v.end(), greater<int>());
cout << "Looking for a 6 ... ";
if(binary_search(v.begin(), v.end(), 6, greater<int>()))
cout << "FOUND!" << endl;
else
cout << "NOT FOUND." << endl;
return 0;
}
看你需要哪个吧。第二种方法没按你的要求书写代码,自己改下哈~
intbinsearch(int*a,intn,inte)/*************a是数组,n是数组大小,e是要查找的元素*/{intlow,mid,high;low=0;high=n-1;while(lowe)high=mid-1;elseif(a[mid]
int binsearch(int *a, int n,int e)/*************a是数组,n是数组大小,e是要查找的元素*/
{
int low,mid,high;
low=0;
high=n-1;
while(low<=high)
{
mid=(low+high)/2;
if(a[mid]>e)
high=mid-1;
else if(a[mid]<e)
low=mid+1;
else
return mid;
}
return -1;
}
/*元素若存在则返回位置,否则返回-1*/
int binsearch(int *a, int n,int e)/*************a是数组,n是数组大小,e是要查找的元素*/
{
int low,mid,high;
low=0;
high=n-1;
while(low<=high)
{
mid=(low+high)/2;
if(a[mid]>e)
high=mid-1;
else if(a[mid]<e)
low=mid+1;
else
return mid;
}
return -1;
}
/*元素若存在则返回位置,否则返回-1*/
扩展阅读:c++教程 ... c++软件 ... c++编程 ... c#简单程序实例 ... c++编程题经典100例 ... c#100个编程实例程序 ... c#面试题 ... c++调用c# ... 常见c++ 流程图 ...