Objectives

By the end of this chapter, you should be able to:

• Implement linear search
• Define divide and conquer algorithms
• Implement binary search

Searching Algorithms

A very common operation that we do when writing code is searching through data. Whether we're digging data in an array or searching through rows in a database, we are often faced with the challenge of how to search most efficiently. The simplest way of searching is an algorithm called linear search. Linear search traverses an array or list until an element is or is not found. When that element is found, the index at which that element exists is returned. If the element is not found, the algorithm returns -1. This is exactly what the indexOf method does for us!

So how do these algorithms perform in terms of their time complexity? This is a linear time algorithm, O(n) since it's possible that you'll need to search the entire array to find the desired element.

Divide and Conquer Algorithms and Binary Search

It might seem like there's no way to improve linear search. After all, if you're trying to find some element among a collection of elements, how can you do better than looking at each element individually and checking whether or not it's the one you're looking for?

Indeed, in general it's hard to do better than linear search. But if you assume an extra condition on your data - namely, if you assume your data is sorted - you can sort through it much more efficiently. We can search through an array of sorted data using an algorithm called binary search.

Binary search is an example of a divide and conquer algorithm, because at each step you're essentially dividing the amount of data you need to look at in half. In computer science it's often easier to solve a smaller problem rather than a larger one. Divide and conquer algorithms do just that! They solve a larger problem by working on a sub-problem, often times recursively.

The idea of binary search is to continually break the problem set in half until you know your answer. The approach takes advantage of the sorted data set. This is critical - if your set isn't sorted, you cannot use binary search to look for elements in it. Here's some psuedocode describing the algorithm:

var searchValue = 1199
index = midpoint of current array
if searchValue == value at index
   return index
if searchValue > value at index
    do binary search of upper half of array
if searchValue < value at index
    do binary search of lower half of array

Since this approach always breaks the problem in half, the runtime is actually O(log(n)), which is significantly faster than O(n) for a large data set.

Want to learn more about these algorithms? Here's a video on linear search; here's one on binary search.

Exercises

Complete all of the exercises here.