【C++数据结构——查找】二分查找（头歌实践教学平台习题）【合集】

#define MAX_SIZE 100  // 定义顺序表的最大容量
template <typename T>
struct SeqList {
    T data[MAX_SIZE];  // 存储数据的数组
    int length;        // 顺序表当前长度
    SeqList() : length(0) {}  // 构造函数初始化长度为 0
};

#include <iostream>
using namespace std;
template <typename T>
void createSeqList(SeqList<T>& list) {
    T num;
    cout << "请输入有序数据（输入 -1 结束输入）：" << endl;
    while (cin >> num && num!= -1) {
        if (list.length < MAX_SIZE) {
            list.data[list.length++] = num;
        } else {
            cout << "顺序表已满，无法继续添加元素。" << endl;
            break;
        }
    }
}

template <typename T>
void printSeqList(const SeqList<T>& list) {
    cout << "顺序表中的元素为：";
    for (int i = 0; i < list.length; i++) {
        cout << list.data[i] << " ";
    }
    cout << endl;
}

int main() {
    SeqList<int> myList;
    createSeqList(myList);
    printSeqList(myList);
    return 0;
}

template <typename T>
int binarySearch(const SeqList<T>& list, T target) {
    int left = 0;  // 左边界
    int right = list.length - 1;  // 右边界
    while (left <= right) {
        int mid = left + (right - left) / 2;  // 计算中间位置，防止溢出
        if (list.data[mid] == target) {
            return mid;  // 找到目标元素，返回其下标
        } else if (list.data[mid] > target) {
            right = mid - 1;  // 在左半部分继续查找
        } else {
            left = mid + 1;  // 在右半部分继续查找
        }
    }
    return -1;  // 未找到目标元素，返回 -1
}

#include <iostream>
#include <vector>
using namespace std;
// 定义查找元素的结构体类型，包含关键字和其他数据（这里暂未详细使用其他数据部分）
struct RecType {
  int key;
  // 可以按需添加其他数据成员及对应操作，此处简化只关注关键字key
};
// 创建顺序表，将输入的关键字数据存入顺序表中
void CreateList(vector<RecType> &R, const vector<int> &keys) {
  for (size_t i = 0; i < keys.size(); ++i) {
    RecType temp;
    temp.key = keys[i];
    R.push_back(temp);
  }
}
// 输出顺序表的函数，遍历顺序表并输出每个元素的关键字
void DispList(const vector<RecType> &R) {
  for (size_t i = 0; i < R.size(); ++i) {
    cout << R[i].key << " ";
  }
  cout << endl;
}
// 二分查找算法实现，按照要求输出每次查找的区间及比较的关键字
int BinSearch(const vector<RecType> &R, int k) {
  int low = 0;
  int high = R.size() - 1;
  int count = 1;
  while (low <= high) {
    int mid = low + (high - low) / 2;
    cout << "  第" << count << "次比较:在[" << low << "," << high
         << "]中比较元素R[" << mid << "]:" << R[mid].key << endl;
    if (R[mid].key == k) {
      return mid + 1; // 返回位置，这里的位置是从1开始计数，所以下标加1
    } else if (R[mid].key > k) {
      high = mid - 1;
    } else {
      low = mid + 1;
    }
    count++;
  }
  return 0; // 如果没找到，返回0表示元素不在表中
}
int main() {
  vector<RecType> R;
  vector<int> keys;
  int n =
      10; // 根据测试示例，这里默认输入数据个数为10，也可以改成让用户输入个数
  cout << "请输入一组数据 :" << endl;
  for (int i = 0; i < n; ++i) {
    int num;
    cin >> num;
    keys.push_back(num);
  }
  CreateList(R, keys);
  cout << "关键字序列:";
  DispList(R);
  int k;
  cin >> k;
  cout << "请输入要查找的关键字 :" << k << endl;
  cout << "查找" << k << "的比较过程如下:" << endl;
  int result = BinSearch(R, k);
  if (result != 0) {
    cout << "元素" << k << "的位置是" << result << endl;
  } else {
    cout << "元素" << k << "不在表中" << endl;
  }
  return 0;
}