Mercurial > hg > ucx / file diff

--- a/src/array_list.c	Tue Sep 17 19:38:41 2024 +0200
+++ b/src/array_list.c	Tue Sep 17 23:11:17 2024 +0200
@@ -236,6 +236,57 @@
     return CX_ARRAY_SUCCESS;
 }
 
+size_t cx_array_binary_search_inf(
+        void const *arr,
+        size_t size,
+        size_t elem_size,
+        void const *elem,
+        cx_compare_func cmp_func
+) {
+    // declare a variable that will contain the compare results
+    int result;
+
+    // cast the array pointer to something we can use offsets with
+    char const *array = arr;
+
+    // check the first array element
+    result = cmp_func(elem, array);
+    if (result <= 0) {
+        return 0;
+    }
+
+    // check the last array element
+    result = cmp_func(elem, array + elem_size * (size - 1));
+    if (result >= 0) {
+        return size - 1;
+    }
+
+    // the element is now guaranteed to be somewhere in the list
+    // so start the binary search
+    size_t left_index = 1;
+    size_t right_index = size - 1;
+    size_t pivot_index;
+
+    while (left_index <= right_index) {
+        pivot_index = left_index + (right_index - left_index) / 2;
+        char const *arr_elem = array + pivot_index * elem_size;
+        result = cmp_func(elem, arr_elem);
+        if (result == 0) {
+            // found it!
+            return pivot_index;
+        } else if (result < 0) {
+            // element is smaller than pivot, continue search left
+            right_index = pivot_index - 1;
+        } else {
+            // element is larger than pivot, continue search right
+            left_index = pivot_index + 1;
+        }
+    }
+
+    // report the largest upper bound
+    return result < 0 ? (pivot_index - 1) : pivot_index;
+}
+
 #ifndef CX_ARRAY_SWAP_SBO_SIZE
 #define CX_ARRAY_SWAP_SBO_SIZE 128
 #endif