常见查找算法介绍及其实现

1. 二分法查找

二分法查找（Binary Search）是一种在有序数组中查找特定元素的算法。其基本思想是将数组分为两部分，然后根据目标元素与中间元素的比较结果，决定在数组的左半部分还是右半部分继续查找。这个过程递归进行，直到找到目标元素或搜索范围为空。

算法特点和应用场景：

• 二分法查找适用于有序数组，且要求数组中的元素是可比较的。
• 二分法查找的时间复杂度为 O(log n) ，其中 n 是数组的长度。

算法步骤：

1. 初始化左右指针，分别指向数组的第一个元素和最后一个元素。
2. 计算中间元素的索引，即 (left + right) / 2 。

3. 比较目标元素与中间元素的大小。

   • 如果目标元素等于中间元素，则返回中间元素的索引。
   • 如果目标元素小于中间元素，则在左半部分继续查找，更新右指针为中间元素的索引减一。
   • 如果目标元素大于中间元素，则在右半部分继续查找，更新左指针为中间元素的索引加一。
4. 重复步骤 2 和 3，直到找到目标元素或搜索范围为空。

简单算法实现：

int binary_search(int arr[], int left, int right, int target) {
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1;
}

实际应用：
在 Tinyexpr 表达式计算库中就有应用，应用于查找对应算法符，代码片段如下：

static const te_variable *find_builtin(const char *name, int len) {
    int imin = 0;
    /* 这里 function 是已经按名称排列好的常量结构体数组 */
    int imax = sizeof(functions) / sizeof(te_variable) - 2;

    /*Binary search.*/
    while (imax >= imin) {
        const int i = (imin + ((imax-imin)/2));
        int c = strncmp(name, functions[i].name, len);
        if (!c) c = '\0' - functions[i].name[len];
        if (c == 0) {
            return functions + i;
        } else if (c > 0) {
            imin = i + 1;
        } else {
            imax = i - 1;
        }
    }

    return 0;
}