feat: Implement expt_0802 binary search

Signed-off-by: KunoiSayami <[email protected]>

1 files changed, 54 insertions, 20 deletions

diff --git a/expt_0802.cpp b/expt_0802.cpp
index 32727fb..fbd6c23 100644
--- a/expt_0802.cpp
+++ b/expt_0802.cpp
@@ -4,11 +4,9 @@
 #include <iostream>
 #include <vector>
 
-using namespace std;
-
-vector<vector<int>> a;
-vector<int> result;
-constexpr size_t LENGTH = 2048;
+std::vector<std::vector<int>> a;
+std::vector<int> result;
+constexpr size_t LENGTH = 1024;
 
 void calculate(int l, int r, int dep) {
   if (l > r)
@@ -20,20 +18,48 @@ void calculate(int l, int r, int dep) {
 }
 
 size_t calculate_location(size_t index) {
-  // auto value = result[index + 1];
-  auto real_index = ++index;
-  int step = 0;
-  while (index > 0) {
-    index /= 2;
-    step++;
-  }
-  auto end = (int)std::pow(2, step - 1);
-  auto location = LENGTH / end / 2 * (real_index % end * 2 + 1);
-  if (location == 0) {
-    location = LENGTH;
+  int step = (int)std::log2(++index) + 1;
+  auto location =
+      LENGTH / (1 << step) * ((index & ((1 << (step - 1)) - 1)) * 2 + 1);
+  return location ? location : LENGTH;
+}
+typedef int key_type;
+
+inline double safeStep(double step) { return step < 0 ? 0 : step; }
+
+int get_son_from_step(int point, bool negative) {
+  return negative ? point * 2 : point * 2 + 1;
+}
+
+const key_type *cudaBinarySearch(key_type *const start, const key_type *end,
+                                 const key_type val) {
+  int step_limit = (int)std::log2(LENGTH) + 1;
+  const auto length = (end - start);
+  key_type *last_known_point = start;
+  auto son = 0;
+
+  for (int i = 0; i < step_limit; i++) {
+    const auto next_level_start = start + (1 << (i + 1)) - 1;
+    /*const auto current_time = (1.0 / (1 << (i + 1)));
+    printf("%d ", *level_start);
+    printf("%d %d\n", *last_known_point, (1 << i));
+    if (*last_known_point == val) {
+      puts("find");
+      return last_known_point;
+    }
+    sum = safeStep(sum +
+                   ((*last_known_point > val) ? -current_time : current_time));
+    last_known_point = level_start + (int)(sum * (double)(1 << i));*/
+    if (*last_known_point == val) {
+      puts("found");
+      return last_known_point;
+    }
+    son = get_son_from_step(son, (*last_known_point > val));
+    last_known_point = next_level_start + son;
+    printf("%d\n", *last_known_point);
   }
-  // printf("%d %d %d %lu %lu\n", step, end, value, real_index % end, location);
-  return location;
+  puts("");
+  return last_known_point;
 }
 
 int main() {
@@ -50,10 +76,18 @@ int main() {
       result.push_back(j);
     }
   }
-  cout << endl;
 
-  for (int i = 0; i < LENGTH; i++) {
+  for (int i = 0; i < 32; i++) {
+    printf("%3d ", i);
+  }
+
+  puts("");
+
+  for (int i = 0; i < 32; i++) {
+    printf("%3d ", result[i]);
     assert(calculate_location(i) == result[i]);
   }
+  puts("");
+  cudaBinarySearch(&result[0], &*result.end(), 1024);
   return 0;
 }