I am trying to solve a tricky algorithm question that has been puzzling me.
Imagine we have a strictly decreasing array of integers and a target value k. We want to find the target value k. This is simple using a search algorithm, however there is another condition. Imagine that, if you check for the value of any number in the array, you increase your penalty p by 1. We want to find the target value, and more importantly, by minimizing the total penalty p that we incur.
Our goal is to have at most p=2 penalty, which could result in a O(sqrt(n)) running time. I am honestly stumped. Does anyone have any idea on how we could go about this?
Here is an example:
[200, 150, 120, 115, 110, 100] Imagine k = 110. We want to have only 2 checks (so that p = 2), with a running time of O(sqrt(n)).
CodePudding user response：
As @Mahrkeenerh said, the widely-accepted "best way" to search in sorted arrays is binary search (in this case fitted to work with reversed arrays). This method, does result in p = 3, given by ceil(log2(6 1)) since the array you gave has 6 elements, but it is the fastest method, especially when the size of the array to search within grows.
Here is a binary search fitted so that it works with backwards arrays.
Given in JavaScript so that it may work as a snippet inside your browser. You may translate it to 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);CodePudding user response：
The best possible way you can find a value inside sorted array is: Binary search