【算法-二分查找】实现过程、C++代码示例以及实际应用

二分查找简介：

也称为折半查找，是一个在已排序数组中查找特定元素的搜索算法。它的工作原理是将有序数组分成两半，然后检查目标值是在左半部分还是右半部分，然后在所选择的那部分中继续查找。这一过程将不断地重复，直到找到目标值或确定目标值不在数组中。

实现过程：

1.初始化两个指针：low 设置为数组的开始位置，high 设置为数组的结束位置。
2.当 low 不大于 high 时，执行以下操作：
-计算中间位置 mid
-如果 array[mid] 是目标值，则返回 mid 位置。
-如果 array[mid] 小于目标值，设置 low 为 mid + 1。
-否则，设置 high 为 mid - 1。
3.如果循环结束还没有返回，那么目标值不在数组中，返回 -1 或其他表示“不在数组中”的值。

一份C++的二分示例如下：

#include <iostream>
#include <vector>

template<typename T>
int binarySearch(const std::vector<T>& sortedArr, T target) {
    int low = 0;
    int high = sortedArr.size() - 1;

    while (low <= high) {
        int mid = low + (high - low) / 2;

        if (sortedArr[mid] == target) {
            return mid;  // 找到目标值，返回其索引
        }
        if (sortedArr[mid] < target) {
            low = mid + 1;  // 查找数组的右侧部分
        } else {
            high = mid - 1;  // 查找数组的左侧部分
        }
    }

    return -1;  // 如果数组中不存在目标值，则返回-1
}


/* compile : g++ binarySerach.cpp -std=c++11 */
int main() {
    std::vector<int> sortedArr {1, 2, 4, 5, 6, 8, 9, 11, 13, 15};

    int target = 9;
    int result = binarySearch(sortedArr, target);

    if (result != -1) {
        std::cout << "Element " << target << " found at index: " << result << std::endl;
    } else {
        std::cout << "Element " << target << " not found in the array." << std::endl;
    }

    return 0;
}

实际应用如redis源码 intset.c

/* Search for the position of "value". Return 1 when the value was found and
 * sets "pos" to the position of the value within the intset. Return 0 when
 * the value is not present in the intset and sets "pos" to the position
 * where "value" can be inserted. */
static uint8_t intsetSearch(intset *is, int64_t value, uint32_t *pos) {
    int min = 0, max = intrev32ifbe(is->length)-1, mid = -1;
    int64_t cur = -1;

    /* The value can never be found when the set is empty */
    if (intrev32ifbe(is->length) == 0) {
        if (pos) *pos = 0;
        return 0;
    } else {
        /* Check for the case where we know we cannot find the value,
         * but do know the insert position. */
        if (value > _intsetGet(is,max)) {
            if (pos) *pos = intrev32ifbe(is->length);
            return 0;
        } else if (value < _intsetGet(is,0)) {
            if (pos) *pos = 0;
            return 0;
        }
    }

    while(max >= min) {
        mid = ((unsigned int)min + (unsigned int)max) >> 1;
        cur = _intsetGet(is,mid);
        if (value > cur) {
            min = mid+1;
        } else if (value < cur) {
            max = mid-1;
        } else {
            break;
        }
    }

    if (value == cur) {
        if (pos) *pos = mid;
        return 1;
    } else {
        if (pos) *pos = min;
        return 0;
    }
}