# Searching and Binary Search

## Course launching November 17, 2020

**Follow me on YouTube** for free coding interview videos.

Users who sign up for the email list will receive an exclusive 75% discount at launch.

Searching refers to finding an item in a data structure. The item may or may not actually exist. For example, find a number in an array of integers.

In this article we'll be focusing on searching linear data structures like arrays, and then in the tree and graph sections, you'll expand on the concepts learned here binary search trees, depth first search, and breadth first search.

## Cheat Sheet

Big O Complexity | |
---|---|

search (sorted) | O(log n) |

search (unsorted) | O(n) |

**Searching in Interviews**

- Unique binary search examples (ex. rotated array, sparse array, no max size)
- Compare multiple sorted arrays (ex. find median of two sorted arrays)
- Search a matrix
- Find duplicates

## Linear Search

Linear search is a naive and brute force approach to finding an item in a data structure. However, sometimes it's the only option we have. We use linear search when we can make no assumptions about the sort or ordering of data, so items can be randomly dispersed and located at any location.

To perform a linear search, you start at the first spot and iterate through the data one-by-one until you find the item you are looking for.
Since we would be required to visit every item in the worst case, it takes *O(n)* time.

## Binary Search

Binary search is basically searching with super powers and gives us *O(log n)* time.

The most important constraint for binary search to work: **the data must be sorted**.

Since our items are ordered, this additional information allows us to be intelligent about how we look for items. Let's imagine a sorted array. If we picked any random item from the list, let's say the middle item, and we compare it to the target we're looking for. If the target is smaller than the random item we pick, we know it must be to the left since the array is sorted. If the target is larger than the random item we pick, we know it must be to the right.

This is the foundation of binary search. We take our input and check the middle item. We can eliminate half the array if our target is larger or smaller. Then with the remaining items, we repeat this process. We take the middle item of this group and compare it with our target and can eliminate half of the remaining items again. This process is repeated until the target is found.

With every step, we eliminate half of the items in the array.
This is how we get *O(log n)* time with binary search.

We are able to find our target in 3 moves even though the input size is 8.

If we increase the input size to 16, it would only take 5 moves for binary search to find the last item, but a linear search would need to visit all `n`

items.

When we compared binary search to linear search in the logarithms article, we saw that binary search still stays very small at large input. For example, at 1048576 it still only takes 20 operations to find a target.

input size n | O(n) | O(log n) |
---|---|---|

2 | 2 | 1 |

4 | 4 | 2 |

8 | 8 | 3 |

16 | 16 | 4 |

... | ... | ... |

1024 | 1024 | 10 |

2048 | 2048 | 11 |

4096 | 4096 | 12 |

... | ... | ... |

1048576 | 1048576 | 20 |

Below is the code to implement a binary search iteratively. We track a start and end number for the bounds, which is initially the entire array. Then when we determine which half our target must be in, we eitner move the lower bound up or the high bound down to the midpoint which eliminates half the items.

We can implement it iteratively as follows:

```
// Iterative Binary Search
function iterativeBinarySearch(array, target) {
let lowerBound = 0;
let upperBound = array.length - 1;
while (lowerBound <= upperBound) {
const midpointIndex = Math.floor((lowerBound + upperBound) / 2);
const midpointItem = array[midpointIndex];
if (target === midpointItem) {
return midpointIndex;
}
if (midpointItem < target) {
lowerBound = midpointIndex + 1;
} else if (midpointItem > target) {
upperBound = midpointIndex - 1;
}
}
return -1;
}
```

Binary search also has a nice recursive solution:

```
// Recursive Binary Search
function recursiveBinarySearch(array, target, lowerBound, upperBound) {
// Base case 1: element not found
if (lowerBound > upperBound) {
return -1;
}
const midpointIndex = Math.floor((lowerBound + upperBound) / 2);
const midpointItem = array[midpointIndex];
// Base case 2: target found
if (midpointItem === target) {
return midpointIndex;
}
// Recursive case: tighten your bounds based on target location
if (midpointItem < target) {
return recursiveBinarySearch(array, target, midpointIndex + 1, upperBound);
}
if (midpointItem > target) {
return recursiveBinarySearch(array, target, lowerBound, midpointIndex - 1);
}
return -1;
}
```

## Additional Resources

Binary search can be understood best visually.

If you need some additional practice or want to prove to yourself that it will always converge on the target, you can use the resources below. I also recommend creating some arrays and walking through binary search by hand.

Table of Contents