Maximus Maximus - 5 months ago 24
Javascript Question

Linear search in the sorted array with the increment of 2 instead of 1

I have a task to implement the

contains
function using linear search that works on the sorted array. I've done it in this way:

function contains(a, e) {
for (let i = 0; i < a.length; i++) {
if (e === a[i]) {
return true;
} else if (e < a[i]) {
return false;
}
}
return false;
}


However, for the task there's a note:


We can make further improvements by incrementing the index at a faster
rate (say, 2). This will reduce the number of comparisons for
searching in the sorted list.


I don't understand how we can do that because we can't skip elements. The only thing that comes to mind is to check current index and previous index:

if (e === a[i] || e === a[i-1]) {


but that's probably not what the author meant. Any ideas?

The example is in the JavaScript language. However I'm interested in the generic solution not specific to any language so you can treat it as a pseudo code.

Answer Source

If your array contains numbers, you can skip every second element if you don't check if the elements are equal, but if you check if the element you search is bigger than the one at your current index.

In every loop you check if array[i] <= a. If it is smaller than a you continue, else you take the value at i-1 and check if this is the value you are looking for. Because the array is sorted, you know at this point that the only position your searched value can be is at i-1.

For Example:

Array: [1, 2, 4, 5, 7, 10]
a: 5

array[0] <= 5 -> true
array[2] <= 5 -> true
array[4] <= 5 -> false

at this point you know that if your value exists in the array, it is between array[2] and array[4], because we know that array[2] < 5 < array[4]

So now you check:

array[3] == 5

If this returns true, your array contains the value, else it doesn't

EDIT I added a code example:

function contains2(a, e) {
  for (let i = 0; i < a.length; i += 2) {
    if (a[i] <= e) {
      continue;
    } else {
      if (a[i-1] === e) {
        console.log(num);
        return true;
     } else if (a[i] === e) {
       return true;
     } else {
       return false;
     }
    }
  }
  return false;
}

This is the implementation. In the JSBin linked below, you can see a comparison of both functions. I added a log to count how often each loop runs. In the given example, your functions needs to run 8 times, because it compares the search value with the values array[0], array[1], array[2], array[3], array[4], array[5], array[6], array[7] until it gives the result. The second functions skips every second entry, so it just compares the search value to array[0], array[2], array[4], array[6], array[8] and then find it at array[7]. That's why it needs less comparisons

https://jsbin.com/vojahoyaju/edit?js,console