编程，让用户输入一个一个账号，检验该账号是否出现在下面的列表中。如果属于下面列表中的账号，则输出合法信息，否则输出非法信息。采用线性查找方法实现该程序。

Question

5658845  4520125  7895122  8777541  8451277  1302850  80801524568555  5552012  5050552  7825877  1250255  1005231  65452313852085  7576651  7881200  4581002
1、算法分析
先用选择排序法装饰所给的账号排序，然后采用二分查找算法检验输入账号的合法性。
2、参考代码
#include<iostream>
using namespace std;
int binarysearch(int a[],int n=10,int value=0000000);
void selectionsort(int a[],int n=10);
int main()
 {    
int test[]={5658845,4520125,7895122,8777541,8451277,1302850,8080152,4568555,5552012,5050552,7825877,1250255,1005231,6545231,3852085,7576651,7881200,4581002};
int accounts;selectionsort(test,18);
cout<<”请输入要查找的账号：”;    
cin>>accounts;    
if(binarysearch(test,sizeof(test)/sizeof(test[0]),accounts))        
cout<<”合法账号！”<<endl;    
else        
cout<<”非法账号！”<<endl;    
return 0;
}
//选择排序函数void selectionsort(int a[],int n)
//二分查找函数int binarysearch(int a[],int n,int value)

Answer 1

#include <iostream>

using namespace std;

void swap(int *a, int *b) {
  int t = *a;
  *a = *b;
  *b = t;
}

void selectionsort(int a[], int n) {
  for (int i = 0; i < n - 1; i++) {
    int min_idx = i;
    for (int j = i + 1; j < n; j++)
      if (a[j] < a[min_idx])
        min_idx = j;
    if (min_idx != i)
      swap(&a[min_idx], &a[i]);
  }
}

int binarysearch(int a[], int n, int value) {
  int left = 0, right = n - 1;
  while (left <= right) {
    int m = (left + right) / 2;
    if (a[m] < value)
      left = m + 1;
    else if (a[m] > value)
      right = m - 1;
    else
      return m;
  }
  return -1;
}

int main() {
  int test[] = {5658845, 4520125, 7895122, 8777541, 8451277, 1302850,
                8080152, 4568555, 5552012, 5050552, 7825877, 1250255,
                1005231, 6545231, 3852085, 7576651, 7881200, 4581002};
  std::size_t size = sizeof(test) / sizeof(int);
  selectionsort(test, size);
  cout << "请输入要查找的账号：";
  int account;
  cin >> account;
  int index = binarysearch(test, size, account);
  if (index >= 0 && index < size)
    cout << "合法账号！" << endl;
  else
    cout << "非法账号！" << endl;
  return 0;
}