feat: Optimize binary search

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

1 files changed, 3 insertions, 6 deletions

diff --git a/expt_0802.cpp b/expt_0802.cpp
index b1a906a..7d520e2 100644
--- a/expt_0802.cpp
+++ b/expt_0802.cpp
@@ -25,10 +25,6 @@ size_t calculate_location(size_t index) {
 }
 typedef int key_type;
 
-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;
@@ -40,7 +36,8 @@ const key_type *cudaBinarySearch(key_type *const start, const key_type *end,
     if (*last_known_point == val) {
       return last_known_point;
     }
-    son = get_son_from_step(son, (*last_known_point > val));
+    // son = get_son_from_step(son, (*last_known_point > val));
+    son = son * 2 + -((*last_known_point - val) >> 31);
     last_known_point = next_level_start + son;
     printf("%d\n", *last_known_point);
   }
@@ -73,6 +70,6 @@ int main() {
     assert(calculate_location(i) == result[i]);
   }
   puts("");
-  cudaBinarySearch(&result[0], &*result.end(), 1024);
+  cudaBinarySearch(&result[0], &*result.end(), 928);
   return 0;
 }