使用最小检查次数查找数组中的值

Question

我正试图解决一个一直困扰我的棘手算法问题。

假设我们有一个严格递减的整数数组和一个目标值k。我们想要找到目标值k。使用搜索算法很简单，但是还有另一个条件。想象一下，如果您检查数组中任何数字的值，则会将惩罚p增加1。我们希望找到目标值，更重要的是，通过最小化我们产生的总惩罚p。

我们的目标是最多罚p=2，这可能会导致O(sqrt(n))的运行时间。我真的被难住了。有人知道我们该怎么做吗？

这里有一个例子：

[200, 150, 120, 115, 110, 100]想象一下k=110。我们希望只有2个检查(因此p=2)，运行时间为O(sqrt(n))。

Answer 1

正如@Mahrkeenerh所说；最佳方式"；在排序数组中搜索是二进制搜索(在本例中适用于反向数组)。这种方法确实会导致p = 3, given by ceil(log2(6+1))，因为您给出的数组有6个元素，但它是最快的方法，尤其是当要在其中搜索的数组的大小增加时。

下面是一个二进制搜索，它适用于后向数组。

在JavaScript中给定，这样它就可以在浏览器中作为一个片段工作。你可以把它翻译成Python。

let p = 0;
const BinarySearch = (arr, x , start=0, end=arr.length) => {
p++;
if(end < start) return -1;
let mid = Math.floor((start + end) / 2);
if(arr[mid] === x) return mid;
if(arr[mid] > x) return BinarySearch(arr, x, mid+1, end);
else return BinarySearch(arr, x , start, mid-1);
};

const MyArray = [200, 150, 120, 115, 110, 100];
console.log("Found at:", BinarySearch(MyArray, 110), 
"Penalty:", p);

Answer 2

在排序数组中查找值的最佳方法是：二进制搜索

https://en.wikipedia.org/wiki/Binary_search_algorithm