Maximus - 5 months ago 24

Javascript Question

I have a task to implement the

`contains`

`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