Data Structures and Algorithms with JavaScript

Chapter 13. Searching Algorithms

Searching for data is a fundamental computer programming task that has been studied for many years. This chapter looks at just one aspect of the search problem—searching for a specified value in a list.

There are two ways to search for data in a list: sequential search and binary search. A sequential search is used when the items in a list are in random order; a binary search is used when the items in a list are in sorted order. Binary search is the more efficient algorithm, but you also have to take into account the extra time it takes to sort the data set before being able to search it for a value.

Commonly Used Functions in Examples

Two functions are commonly used in multiple examples in this chapter.

The first is dispArr(), which displays array contents, just as was used in Chapter 12.

function dispArr(arr) {
  for (var i = 0; i < arr.length; ++i) {
     putstr(arr[i] + " ");
     if (i % 10 == 9) {
        putstr("\n");
    }
  }
  if (i % 10 != 0) {
     putstr("\n");
  }
}

The second is insertionsort(), which preprocesses array entries, enabling more efficient searches.

function insertionsort(arr) {
   var temp, inner;
   for (var outer = 1; outer <= arr.length-1; ++outer) {
      temp = arr[outer];
      inner = outer;
      while (inner > 0 && (arr[inner-1] >= temp)) {
         arr[inner] = arr[inner-1];
         --inner;
      }
      arr[inner] = temp;
   }
}

Incorporate the code for either when called for in the example. === Sequential Search

The most obvious way to search for data in a list is to begin at the first element ...