Binary Searching

I will explain the ordinary search function. I will then demonstrate the binarySearch function. Next I give the algorithm and then the function (code). I use letters of the alphabet to do most of the explanation. Finally, I show you how the BinarySearch function works with strings.

The Ordinary Search

The ordinary search function simply iterates through an array until it finds what you are looking for.

Before I continue, let me talk about the “return” statement. This statement is not only used with the JavaScript language, it is used with C++ and other languages. If the “return” statement is in a function, during execution, when the function reaches the point with the statement, the function stops and gives control to the calling function. This means that any other thing below the return statement is not executed. Even another return statement is not executed. As control is given to the calling function, the called function can also give a result from what it has processed, to the calling function.

In my implementation of the ordinary search function, if the function sees the element, it returns the corresponding index in the array. If it does not see the element, it returns the length of the array. This is the implementation.

function ordinarySearch(theList, key)

{

for (i=0; i<theList.length; ++i)

{

if (theList[i] == key)

return i;

}

return theList.length;

}

The element you are looking for is called the key. The function takes the name of the array and the element (key) you are looking for as arguments. The function then goes into a for-loop, and beginning from the first element, it compares the key with the element of the index. When the function sees the element, it returns the index of the key seen in the array. If the function goes through the array completely, and does not see the key, it returns the length of the array.

You may ask why we do not allow the function to complete the iteration; why should we return the index as soon as the key is seen? This is to reduce processing time. Imagine that the key is the first element in the array. Going through (comparing) the rest of the elements would simply be a waste of time.

If the function does not see the key in the for-loop, it will not return because of the “if” condition. The execution of the function will continue. As such, the second return statement “return theList.length” will ultimately be executed.