JavaScript Searching Algorithms

Linear search

Linear search is a simple search algorithm that looks for a specific item (the “search key”) within a larger data set by examining each element in the data set one by one, until it finds the search key or determines that the search key is not present.

function linearSearch(array, item) {
  for (let i = 0; i < array.length; i++) {
    if (array[i] === item) {
      return i;
    }
  }
  return -1;
}

To understand how this function works, let’s walk through an example. Suppose we have the following array of integers and we want to find the index of the number 5:

[1, 3, 5, 7, 9]

The first thing the linear search function does is initialize a loop that will iterate over each element in the array. The loop is controlled by the variable i, which starts at 0 and increments by 1 on each iteration.

On the first iteration of the loop, i is 0, so the function checks the value of array[0], which is 1. Since 1 is not equal to 5, the function continues to the next iteration of the loop.

On the second iteration, i is 1, so the function checks the value of array[1], which is 3. Again, this value is not equal to 5, so the function continues to the next iteration.

On the third iteration, i is 2, so the function checks the value of array[2], which is 5. Since 5 is equal to 5, the function returns the value of i, which is 2. This is the index of the number 5 in the array.

If the search key is not found, the function will reach the end of the array without finding a match, and will return -1 to indicate that the search key was not found.

let array = [1, 3, 5, 7, 9];
console.log(linearSearch(array, 3)); // Outputs: 1
console.log(linearSearch(array, 7)); // Outputs: 3
console.log(linearSearch(array, 4)); // Outputs: -1

The first call to linearSearch() will return 2, because 5 is located at index 2 in the array. The second call will return 3, because 7 is located at index 3 in the array. The third call will return -1, because 4 is not present in the array.

Binary search

Binary search is an efficient search algorithm that works by dividing a sorted data set in half and comparing the search key to the value at the midpoint. If the search key is not found, the algorithm repeats the process with either the left or right half of the data set, depending on the value of the search key. This process is repeated until the search key is found or it is determined that the key is not present in the data set.

function binarySearch(array, item) {
  let low = 0;
  let high = array.length - 1;
  let mid;

  while (low <= high) {
    mid = Math.floor((low + high) / 2);
    if (array[mid] === item) {
      return mid;
    }
    if (array[mid] < item) {
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }
  return -1;
}

To understand how this function works, let’s walk through an example. Suppose we have the following sorted array of integers and we want to find the index of the number 7:

[1, 3, 5, 7, 9]

The first thing the binary search function does is initialize the variables low and high to the indices of the first and last elements in the array, respectively. It also initializes the mid variable to the index of the middle element in the array.

The function then enters a loop that will continue as long as low is less than or equal to high. On the first iteration of the loop, low is 0, high is 4, and mid is 2.

The function compares the value of array[mid], which is 5, to the search key, which is 7. Since 5 is less than 7, the function updates the value of low to be mid + 1, which is 3. This effectively narrows the search space to the right half of the array.

On the second iteration of the loop, low is 3, high is 4, and mid is 3. The function compares the value of array[mid], which is 7, to the search key, which is also 7. Since they are equal, the function returns the value of mid, which is 3. This is the index of the number 7 in the array.

If the search key is not found, the function will eventually reach a point where low is greater than high, in which case it will exit the loop and return -1 to indicate that the search key was not found.

let array = [1, 3, 5, 7, 9];
console.log(binarySearch(array, 3)); // Outputs: 1
console.log(binarySearch(array, 7)); // Outputs: 3
console.log(binarySearch(array, 4)); // Outputs: -1

The first call to binarySearch() will return 2, because 5 is located at index 2 in the array. The second call will return 3, because 7 is located at index 3 in the array. The third call will return -1, because 4 is not present