By the end of this chapter, you should be able to:
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.
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.
Complete all of the exercises here.
When you're ready, move on to Basic Sorting Algorithms