SearchBlock.cc

#include <algorithm>
#include <cassert>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <span>

#include "vector.hh"

// 线性查找
template <typename compar>
int linearSearch(const compar &key, std::span<const compar> A) {
  for (int i(0), sz(A.size()); i < sz; ++i)
    if (A[i] == key) return i;
  return -1;
}

// 分块查找
template <typename compar>
int blockSearch(const compar &key, std::span<const compar> A) {
  assert(std::ranges::is_sorted(A));
  int n = A.size(), block = 1;
  while (block * block <= n) block++;

  int hi = 0;
  for (; hi < n; hi += block) {
    if (key < A[hi]) break;
  }

  if (hi > 0) {
    int i{hi - block};
    if (n <= hi) hi = n;
    for (; i < hi; i++)
      if (key == A[i]) return i;
  }

  return -1;
}

int main() {
  std::srand(std::time(nullptr));
  ns::vector<int> vec{1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29};

  int num{std::rand() % vec.back()};
  std::cout << "target\t" << num << '\n';
  std::cout << "vector\t";
  for (const auto &e : vec) std::cout << e << '\t';
  std::cout << '\n';

  int r{linearSearch<int>(num, vec)};
  std::cout << "linear\t";
  if (r != -1) {
    for (int i = 0; i < r; ++i) std::cout << '\t';
    std::cout << vec[r];
  } else
    std::cout << r;
  std::cout << '\n';
  assert(linearSearch<int>(vec.front() - 1, vec) == -1);
  assert(linearSearch<int>(vec.back() + 1, vec) == -1);

  int s{blockSearch<int>(num, vec)};
  std::cout << "block\t";
  if (s != -1) {
    for (int i = 0; i < s; ++i) std::cout << '\t';
    std::cout << vec[s];
  } else
    std::cout << s;
  std::cout << '\n';
  assert(blockSearch<int>(vec.front() - 1, vec) == -1);
  assert(blockSearch<int>(vec.back() + 1, vec) == -1);

  assert(r == s);
}