时间戳

首页 > 解决方案 > 返回索引的递归二分查找

python - 返回索引的递归二分查找

问题描述

我正在介绍 CS 课程，并被分配执行递归二进制搜索，该搜索返回搜索项目的索引，如果它存在于列表中，否则它应该返回负数。

对该函数进行分类的代码如下：（python代码）

numList = [1,2,3,4,5,...6,7,8,9]
key = <insert number to search for here>
position = binarySearch(numList, key)
print("Your number is at " + str(position))

我不允许修改函数的参数。

给定

def binarySearch(numList, key):
   <code here>

关于如何做到这一点的任何提示？我似乎总是无法恢复原始号码的索引。二分查找必须是递归的。

标签： pythonrecursionbinary-search

解决方案

从geeksforgeeks复制二进制搜索

根据问题陈述实现代码

numList = [1,2,3,4,5,6,7,8,9]
key = 6

def binarySearch(numList, key):
    def binary_search(alist, start, end, key):
        """Search key in alist[start... end - 1]."""
        if not start < end:
            return -1

        mid = (start + end)//2
        if alist[mid] < key:
            return binary_search(alist, mid + 1, end, key)
        elif alist[mid] > key:
            return binary_search(alist, start, mid, key)
        else:
            return mid
    return binary_search(numList, 0, len(numList), key)

print(binarySearch(numList, key)) # otput 5, index start from 0

推荐阅读