67 lines
2.4 KiB
C
67 lines
2.4 KiB
C
|
#ifndef INCLUDED_C_BINARYSEARCH_H
|
||
|
|
#define INCLUDED_C_BINARYSEARCH_H
|
||
|
|
|
||
|
|
#ifndef INCLUDED_C_TYPES_H
|
||
|
|
#include <c_Types.h>
|
||
|
|
#endif /*INCLUDED_C_TYPES_H*/
|
||
|
|
|
||
|
|
|
||
|
|
/* ------------------------------------------------------------------------------------------------------------------ */
|
||
|
|
/* */
|
||
|
|
|
||
|
|
/**
|
||
|
|
* @brief 工业级泛型二分查找算法 (类似于标准库 bsearch)
|
||
|
|
*
|
||
|
|
* @param key 指向待查找目标对象的指针
|
||
|
|
* @param base 指向已排序连续数组首元素的指针
|
||
|
|
* @param num 数组中元素的总个数
|
||
|
|
* @param size 每个元素所占用的内存字节大小 (sizeof)
|
||
|
|
* @param cmp 比对回调函数指针 (不能为 NULL)
|
||
|
|
* @return const void* 找到时返回指向数组中匹配元素的泛型指针；未找到或参数非法时返回 NULL
|
||
|
|
*/
|
||
|
|
C_STATIC_FORCE_INLINE
|
||
|
|
const void* c_BinarySearch(const void* key,
|
||
|
|
const void* base,
|
||
|
|
c_size_t num,
|
||
|
|
c_size_t size,
|
||
|
|
int (*cmp)(const void* key, const void* elem))
|
||
|
|
{
|
||
|
|
// 边界与防御性校验
|
||
|
|
if (!key || !base || num == 0 || size == 0 || !cmp) {
|
||
|
|
return NULL;
|
||
|
|
}
|
||
|
|
|
||
|
|
const char* array_base = (const char*)base;
|
||
|
|
|
||
|
|
// 🌟【安全加固核心】：采用 c_size_t 无符号左闭右开控制流
|
||
|
|
c_size_t low = 0;
|
||
|
|
c_size_t high = num; // 右边界设为 num（开区间），high 永远不需要自减，物理杜绝下溢
|
||
|
|
|
||
|
|
while (low < high) { // 🌟 注意：开区间控制条件为 low < high，而不是 <=
|
||
|
|
// 采用防算术溢出的中间索引计算法
|
||
|
|
c_size_t mid = low + ((high - low) >> 1);
|
||
|
|
|
||
|
|
// 计算当前 mid 元素在扁平内存中的绝对指针位置
|
||
|
|
const void* mid_elem = (const void*)(array_base + (mid * size));
|
||
|
|
|
||
|
|
// 执行用户自定义比对
|
||
|
|
int cmp_res = cmp(key, mid_elem);
|
||
|
|
|
||
|
|
if (cmp_res == 0) {
|
||
|
|
return mid_elem; // 精确命中，返回该元素的内存首地址
|
||
|
|
}
|
||
|
|
else if (cmp_res < 0) {
|
||
|
|
// 🌟【核心修正】：目标在左侧低位半区，直接收缩右开边界为 mid。
|
||
|
|
// 彻底干掉了原先“high = mid - 1”引发的 UINT64_MAX 死循环隐患！
|
||
|
|
high = mid;
|
||
|
|
}
|
||
|
|
else {
|
||
|
|
low = mid + 1; // 目标在右侧高位半区，安全单调向右靠拢
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
return NULL; // 未在已排好序的数组中检索到目标
|
||
|
|
}
|
||
|
|
|
||
|
|
#endif /*INCLUDED_C_BINARYSEARCH_H*/
|