koala, тут треба мiркувати. По формi менi ваш алгоритм до вподоби. Двовимiрне поле пошуку - двовимiрна рекурсiя.
Але я хочу повернутися до попереднього питання. Я вчора (та й сьогоднi) вже трохи втомлений. Тому даруйте менi певну недбалiсть у кодi що буде далi. Але спочатку мої аргументи. Я дарма згодився з вашими, останнього разу. Ви казали що виконуватиметься лише одна гiлка if. А це не так. I саме тому, що логiчнi вирази у першому if в данному випадку мають бути виконани всi. Бо логiчне або не припине перевiрку пiсля першого false. Тож у навiть половинi випадкiв буде 3 виклика, а у найгiршому, - 4.
Ще гiрше те, що основання логарифму значно блище до 1 анiж 2...
Менi дуже шкода. Правда. Єдина надiя, що я десь помилився:
#include <iostream>
#include <algorithm>
#include <random>
#include <chrono>
template<typename It>
void uniform_random_fill(int num_min, int num_max, It first, It last) {
std::random_device r;
std::mt19937 g(r());
std::uniform_int_distribution<int> ud(num_min, num_max);
while(first != last) *first++ = ud(g);
}
std::vector<int> make_source_vector(int num_min, int num_max, unsigned v_size) {
std::vector<int> vec(v_size);
uniform_random_fill(num_min, num_max, vec.begin(), vec.end());
return vec;
}
std::vector<std::vector<int>> make_matrix(int num_min, int num_max, unsigned v_size) {
std::vector<std::vector<int>> matrix;
auto vec = make_source_vector(num_min, num_max, v_size);
for(int el : vec) {
for(int &el : vec) el += 1;
std::sort(vec.begin(), vec.end());
matrix.push_back(vec);
}
return matrix;
}
void print_matrix(std::vector<std::vector<int>> const &v) {
for(const auto &el : v) {
for(const int in : el)
std::cout << in << ' ';
std::cout << '\n';
}
std::cout << '\n';
}
struct simple_timer {
~simple_timer() {
std::chrono::duration<double> dur = std::chrono::steady_clock::now() - begin;
std::cout << "\nThe time span was: " << dur.count() << "\n";
}
std::chrono::time_point<std::chrono::steady_clock> begin =
std::chrono::steady_clock::now();
};
template<typename T>
// std::pair<int, int>
bool find_in_matrix(
const std::vector<std::vector<T>> &matrix,
const T &target
) {
int row_ind(0);
for(const auto &vec : matrix) {
if(vec.front() <= target && vec.back() >= target) {
auto it = std::lower_bound(vec.begin(), vec.end(), target);
if(*it == target) {
return true;
// { row_ind, it - vec.begin() };
}
}
++row_ind;
}
return false;
// { -1, -1 };
}
class Solution {
public:
using Matrix = std::vector<std::vector<int>>;
bool searchMatrix(const Matrix &matrix, int target) {
return searchMatrix(matrix, target, 0, matrix[0].size(), 0, matrix.size());
}
bool searchMatrix(const Matrix &matrix, int target, int x0, int x1, int y0, int y1) {
if(x1 == x0 || y1 == y0)
return false;
if(x1 - x0 == 1 && y1 - y0 == 1)
return matrix[y0][x0] == target;
int xmid = (x0 + x1) / 2;
int ymid = (y0 + y1) / 2;
if(matrix[ymid][xmid] == target)
return true;
else if(matrix[ymid][xmid] > target)
return searchMatrix(matrix, target, x0, xmid, ymid, y1)
|| searchMatrix(matrix, target, x0, x1, y0, ymid);
else
return searchMatrix(matrix, target, x0, xmid + 1, ymid + 1, y1)
|| searchMatrix(matrix, target, xmid + 1, x1, y0, y1);
}
};
const int num_min = 0;
const int num_max = 10;
const int v_size = 1000; // 10
const int search_number = 10000; // 5
int main() {
std::vector<std::vector<int>>
matrix(make_matrix(num_min, num_max, v_size));
std::vector<int> vtargets=make_source_vector(num_min, 2*num_max, search_number);
std::cout << "\nfind_in_matrix\n";
{
simple_timer st;
for(auto target : vtargets) {
bool res=find_in_matrix(matrix, target);
// cout << res << '\n';
}
}
std::cout << "\nSolution\n";
Solution sol;
{
simple_timer st;
for(auto target : vtargets) {
bool res = sol.searchMatrix(matrix, target);
// cout << res << '\n';
}
}
return 0;
}
Даруйте що не вiдформатував i може десь залишилося трохи робочого смiття. I за те що багатенько слiв, але ужати поки не вийшло.
