对未排序列表进行二进制搜索

本文介绍了对未排序列表进行二进制搜索的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我需要对一个数字列表使用二进制搜索，并让它返回该数字的索引。在列表未排序的情况下如何执行此操作？我需要返回未排序列表的索引，而不是排序列表。

推荐答案

您需要对列表的副本进行排序，并将索引列表维护回原始列表。

一种方法是使用decorate-sort-undecorate idiom：

>>> values = [5, 2, 7] >>> decorated = list(zip(value, range(len(values)))) >>> sorted_decorated = sorted(decorated) >>> sorted_values, indices = list(zip(sorted_decorated)) >>> sorted_values [2, 5, 7] >>> indices [1, 0, 2]

然后您可以对排序值执行二进制搜索，您就可以将索引映射回原始索引。

您可以使用bisect模块implement binary search：

def index(a, x): 'Locate the leftmost value exactly equal to x' i = bisect_left(a, x) if i != len(a) and a[i] == x: return i raise ValueError

使用它：

>>> index(sorted_values, 5) 1

因此原始索引为：

>>> indices[1] 0