c++与python实现二分查找的原理及实现-C/C++开发

本文介绍了c++与python实现二分查找的原理及实现，二分查找指首先将数组中间值和目标值进行比较，如果相等则返回；如果不相等，则选择中间值左边的一半或者右边的一半进行比较；不断重复直到检索完毕，下文相关资料需要的朋友可以参考一

二分查找的核心思想是：首先将数组中间值和目标值进行比较，如果相等则返回；如果不相等，则选择中间值左边的一半或者右边的一半进行比较；不断重复直到检索完毕。首先来看下面这个gif，其中蓝色圈表示左位置，粉色圈表示右位置，绿色圈表示中间位置：

IiBzcmM9

首先定义的是左边界（蓝色圈）和右边界（粉色圈），进而根据左边界和右边界计算出中间位置（绿色圈）；然后，比较中间位置的值和目标值的大小，比较结果包含3种情况

如果相等则表示查找成功，返回中间位置；
如果中间位置的值小于目标值，则说明目标值在中间位置到右边界这一半；
如果中间位置的值大于目标值，则说明目标值在左边界到中间位置这一半；

上述步骤的循环需要终止条件，即左边界小于或等于右边界，表明此时已经搜索完成，目标数值不在数据中存在。

1、时间复杂度与优缺点

既然每次搜索后区间长度都减半，假设数据个数（即区间长度）为n，那么算法每次迭代得到的区间长度依次为n/2，n/4，n/8等等，其通项如下，k表示循环次数：

IiBzcmM9

最坏的情况，就是搜索到区间长度为1，即最后只剩1个元素：

IiBzcmM9

所以，可以求得最坏情况下需要运行的次数为：

IiBzcmM9

因此二分查找复杂度为O(logn)，相比于顺序查找其速度获得了极大的提高（优点）。但是，必须注意二分查找需要保证数据是有序的，这就要求数据必须预先进行排序（缺点）。

2、python实现

def binary_search(ordered_list, target_value):
    """
    Args:
        ordered_list: data with order
        target_value: value that want be searched
    """
    left = 0
    right = len(ordered_list)-1
    # 终止条件
    while left <= right:
        # 中间位置计算
        mid = int((left+right)/2)
        if ordered_list[mid] == target_value:
            return "index is {}, target value is {}".format(mid, ordered_list[mid])
        # 此时目标值在中间值右边，更新左位置
        elif ordered_list[mid] < target_value:
            left = mid + 1
        # 此时目标值在中间值左边，更新右位置
        elif ordered_list[mid] > target_value:
            right = mid - 1
    # 搜索结束没有找到
    return "Not find"

3、C++实现

int binarySearch(int *orderedData, int dataLength, int targetValue) {
    int left = 0;
    int right = dataLength - 1;
    int mid;
    // 终止条件
    while (left<=right)
    {
        // 中间位置计算
        mid = (left + right) / 2;
        if (*(orderedData + mid) == targetValue) {
            return mid;
        }
        // 目标值在中间值右边，更新左位置
        else if (*(orderedData + mid) < targetValue){
            left = mid + 1;
        }
        // 目标值在中间值左边，更新右位置
        else
        {
            right = mid - 1;
        }
    }
    // 搜索不到，返回-1
    return -1;
}

到此这篇关于c++与python实现二分查找的原理及实现的文章就介绍到这了,更多相关c++与python实现二分查找内容请搜索编程学习网以前的文章希望大家以后多多支持编程学习网！