Search for a key in an array in which consecutive numbers differ by + 1 / -1

Question

For a one-dimensional array. Each number in this array differs from a numbered number by +1 or -1. Example: array {5,6,7,6,5,6,7,8,9,8}

You are given a number to search for its first occurrence in this array (example: search 8 - your code should return 7). Do not use linear search.

Without a linear search, I could try this as follows:

Check if (array[0] == Key) { YES: return 0; } Take a variable: Diff = array[0] // Keep on traversing the array, if Next Number>Current Number Diff += 1 Else Diff -= 1 if (Diff==key) { return current_index+1; } 

But this method is too general. Even if the difference between the keys is NOT + -1, but something else, this method will solve this problem.

What is the specific + -1 difference that can give me a better solution?

Thanks.

Answer 1

Let's say that you are looking for 16, and array [0] = 8. This means that the number you are looking for cannot appear in front of array [8], i.e. (target - array [0]). So you read the array [8], which has 13; this means that the target cannot appear in front of the array [11]. And so on. The difference +/- 1 allows you to skip ahead in the search because you know that if array [x] = (target +/- N), that target number cannot appear before the array [x + N].

Answer 2

The selected answer is not optimal. If you are trying to minimize the number of probes (array search), you can do better than searching from the very beginning, and the steps that reach the whole `target - array[i]

Since you are allowed to do random access using indexed searches, you can make much more progress. For example, if you are looking for 9 in an array that starts with a[0] = 0 , you can examine a[16] to see if it is less than or equal to 0. If not, then none of a[0 .. 16] may reach 9.

Big steps give you more information for each probe (each probe allows you to exclude signs both on the left and on the right). This allows you to get twice as much information for each probe when compared to the minimum steps when searching on the left.

To demonstrate the benefits of search-from-mid compared to search-from-left, here is some working code written in the Python programming language:

 def find(arr, value, bias=2): # With the bias at 2, new probes are in the middle of the range. # Increase the bias to force the search leftwards. # A very large bias does the same as searching from left side of the range. todo = [(0, len(arr)-1)] # list of ranges where the value is possible while todo: low, high = todo.pop() if low == high: if arr[low] == value: return low else: continue mid = low + (high - low) // bias diff = abs(arr[mid] - value) if mid+diff <= high: todo.append([mid + diff, high]) if mid-diff >= low: todo.append([low, mid - diff]) raise ValueError('Value is not in the array') 

Conceptually, what the algorithm does is an attempt to obtain the maximum amount of information possible with each probe. Sometimes he is lucky and immediately exclude large ranges; sometimes it will be unsuccessful and will only be able to eliminate a tiny subrange. Regardless of luck, his exclusion zone will be twice as large as the search from the left.

Simple test code:

 arr = [10, 11, 12, 13, 14, 13, 12, 11, 10, 9, 8, 7, 6, 7, 8] for i in range(min(arr), max(arr)+1): assert arr.index(i) == find(arr, i) 

Answer 3

You do not need to look at every number in the list. Suppose you are looking for 8 , and the first number is 5 . You can safely complete step 3 since 8 cannot be completed in less than three steps. You might consider taking a step a little more - say, 6 - since there are probably some -1, but I don’t know if it will be more efficient, since you will not be sure that this is the “first” occurrence. So let's stick with the original:

When you switch to a new number, you determine which size step you need to take next - in the above example, if you did step 3, you would find 6, step 2 more (8-6), and you will again find 6, step 2 more and you will find 8 - you are there! You know that this is the first occurrence, since the numbers you missed could not be 8. And only three steps instead of seven.