要求：
1.若查找成功，返回元素在有序数组中的位置和查找次数；
2.若查找失败，返回出错标志和查找次数。
//low应从0开始，因为设置的数组下标从0开始 //虽然mid不变，但是当key为首元素时，mid为1也就是第二元素，导致找不到第一个元素。 #include <iostream> using namespace std; typedef int Status; typedef int KeyType; typedef int InfoType; typedef struct { KeyType key; InfoType otherinfo; }ElemType; typedef struct { ElemType* R; int length; }SSTable; //对顺序表初始化 Status InitSSTable(SSTable& ST) { ST.R = new ElemType[100]; if (!ST.R) exit(OVERFLOW); ST.length = 0; return 1; } //顺序表的建立 void CreateSSTable(SSTable& ST) { int n; cout << "请输入顺序表的元素个数:"; cin >> n; cout << "请依次输入元素:"; for (int i = 0; i < n; i++) { cin >> ST.R[i].key; ST.length++; } } //顺序表的显示 Status SSTableShow(SSTable ST) { for (int i = 0; i < ST.length; i++) { cout << ST.R[i].key << " "; } cout << endl; return 1; } //折半查找 int count0; Status Search_Bin(SSTable ST, KeyType key) { int low = 0; int high = ST.length-1; int mid = 0; while (low<=high) { count0++; mid = (low + high) / 2; if (key == ST.R[mid].key) { return mid+1; } else if (key<ST.R[mid].key) { high = mid - 1; } else { low = mid + 1; } } return -1; } int main() { SSTable ST; InitSSTable(ST); CreateSSTable(ST); SSTableShow(ST); int key; cout << "输入要查找的元素："; cin >> key; int address = Search_Bin(ST, key); if (address == -1) { cout << "查找失败,查找次数为:"<<count0; } else { cout << "该元素在" <<address<<"号位置。"<<"比较"<<count0<<"次"<< endl; } return 0; }