In our line of work, we often have to perform one specific task – getting the index number of a certain array element. Sometimes we need its exact location in the array, so we use indexOf(). Other times, we only need to find out if it exists, so we use contains() (for strings only, or includes(), when not confined by ServiceNow). But there has to be a better way, right? 

OK, let’s take a step back for a moment. What’s wrong with indexOf(), you might ask. Nothing really if we have a relatively small, unsorted array. The problem comes when the array size increases. Let me give you an example: 

var myAwesomeNumbersArray = [3, 1, 6, 17, 4, 9, 16, 10, 23, 5];

We have to find the index of 4.  So, we would do something like this: 

function findMeAnIndex(array, element) {
    
    for(var i in array) {
        if(array[i] === element) {
            return i
        }
    };

    return -1;

}

In this case, we’ll need five iterations to get to what we’re looking for. If we’re searching the index of 5, we’ll have to go through the whole array. So, we can easily see that with this method the complexity increases in a linear fashion with the size of the array.  

But why would I use this method when I have indexOf()? 

Well, that piece of code is pretty much what indexOf() is doing. And includes() too. And their ServiceNow cousin contains() also, although it only deals with strings. All these have a complexity of O(n). 

The truth is, with an unsorted array, there’s nothing much we can do about it. But what if we can get a sorted array. That’s where the fun begins: 

var myEvenMoreAwesomeArray = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10];

Programmers have a special sense that tells them if something can be used in a more efficient way.  This results in the following: 

function binarySearch(array, element) {

    var lowerEnd = 0;

    var upperEnd = array.length - 1;

    while(lowerEnd <= upperEnd) {
        var midElement = lowerEnd + Math.floor((upperEnd - lowerEnd) / 2);

        if(element === array[midElement]) {
            return midElement;
        }

        if(element < array[midElement]) {
            upperEnd = midElement - 1;
        } else {
            lowerEnd = midElement + 1;
        }
    }

    return -1;
}

Let’s go through what we’ve just witnessed. It’s a simple function, it takes an array, and an element we’re searching for in that array. We know already that the array is sorted. Otherwise, this just won’t work. 

We take the first and last index of the array. We always start with 0 as the first index (lowerEnd), and array length-1, in this case, 10 (upperEnd). Then we do the following: 

1. We take those two’s middle element index; 

2. We floor it in case it’s not an integer; 

3. We check if this middle element is the index we’re looking for. If yes, we return it; 

4. If not, we check if the wanted element is on the left or on the right of the middle (if it’s smaller or bigger); 

5. We move the upper or lower limit accordingly, effectively cutting the initial array in half, never again bothering with the half we know for sure does not contain our value; 

6. Repeat until: 
   a. the value is found; 
   b. the upper end becomes smaller than or equal to the lower one, after which we return -1 (no such element found); 

Let’s say we have to find the index of 8 in myEvenMoreAwesomeArray. Here’s how it would go: 

7. Initially, we’ll start with lowerEnd of 0 and upperEnd of 10; 

8. The midElement of those would be 0 + (10 – 0) / 2, or 5; 

9. We check if we have number 8 on index 5; 

10. We find out that we don’t and that our wanted element is bigger than the middle one; 

11. We then proceed with the right half of the array – the lower limit becomes 5 + 1, and the upper remains 10; 

12. The new middle element becomes 6 + (10 – 6) / 2, or 8; 

13. We check if we have our wanted element, 8, on index 8 of the array, and just like that we’re done in two iterations. 

If we had used the standard method (indexOf()), we would have iterated 9 times to reach our goal. Or, as we would say, our approach has a complexity of O(log(n)). 

Now you can go and make this thing a method in a utils Script Include of whatever instance you’re working in.  

For more useful insights, check out our latest article regarding the implementation of a 3-strike rule in ServiceNow.