【算法】二分查找

小嗷犬

发布于 2022-11-15 15:47:40

2870

发布于 2022-11-15 15:47:40

文章被收录于专栏：小嗷犬的CSDN文章

本文为自用模板，不提供思路讲解

二分查找

简介

二分查找，用于查找有序组中特殊值的位置，时间复杂度为O(logn)。

C++ 实现

二分查找的 C++ 实现：

int binSearch(int *arr, int n, int target)
{
    int left = 0, right = n - 1;
    while (left <= right)
    {
        int mid = left + (right - left) / 2;
        if (arr(mid) == target)
        {
            return mid;
        }
        else if (arr(mid) > target)
        {
            right = mid - 1;
        }
        else
        {
            left = mid + 1;
        }
    }
    return -1;
}

Python 实现

二分查找的 Python 实现：

def bin_search(data_list, target):
    left = 0
    right = len(data_list) - 1
    while left <= right:
        mid = left + (right - left) // 2
        if data_list[mid] == target:
            return mid
        elif data_list[mid] > target:
            right = mid - 1
        else:
            left = mid + 1
    return -1

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2022-10-03，如有侵权请联系 cloudcommunity@tencent.com 删除

python