# Linear & Binary Search

Learn the concepts behind linear and binary search before implementing them in Python. Test your knowledge with two quizzes.

Start- 1
Imagine that you are a DJ at a party. The diagram on the right shows your playlist for the event. A party guest wants to know if “Uptown Funk” by Bruno Mars is a song on your playlist. You would ...

- 2
Linear search can be used to search for a desired value in a list. It achieves this by examining each of the elements and comparing it with the search element starting with the first element to the...

- 3
Linear search is not considered the most efficient search algorithm, especially for lists of large magnitudes. However, linear search is a great choice if you expect to find the target value at the...

- 4
There are two worst cases for linear search.

**Case 1:**when the target value at the end of the list. ![](https://s3.amazonaws.com/codecademy-content/courses/search-course/visualizations/worst+... - 5
If this search was used 1000 times on a 1000 different lists, some of them would be the best case, some the worst. For most searches, it would be somewhere in between. On average it would be in t...

- 6
Linear search runs in linear time. Its efficiency can be expressed as a linear function, with the number of comparisons to find a target increasing linearly as the size of the list, N, increases. ...

- 7
**Congratulations!**You have learned how linear search works and how to use it to search for values in lists. Let’s review what we learned: * Linear search is a search algorithm that sequentia...

- 1
With a sorted data-set, we can take advantage of the ordering to make a sort which is more efficient than going element by element. Let's say you were looking up the word "Telescope" in the dictio...

- 2
Play with this interactive visualization demonstrating binary search. Refresh the page to play again with a different list.

- 3
How efficient is binary search? In each iteration, we are

**cutting the list in half.**The time complexity is [...] . A sorted list of [...] elements will take**at most**[...] [...] [...

- 1
The

*linear search*algorithm checks whether a value is an element in a list by scanning the elements of a list one-by-one. The algorithm’s iterative approach to finding a target value is useful... - 2
Linear search is used to search for a target value in a list. We examine each of the elements in the list and compare them with the target value until matching the target. If a match is found, the...

- 3
In the text editor, you will find the code for the [...] function that we implemented in Python. When called, our function returns either an index of an element that matches the target value or...

- 4
With a few changes to our code, we can modify linear search to solve more complex search problems. Our linear search function, [...] , currently finds whether one given value exists in a list, re...

- 5
The largest value of a sorted list conveniently is the last element of a list. The largest value of an unsorted list, however, is not guaranteed to be the last element. Imagine that you are a te...

- 6
You are a linear search whiz! You have implemented linear search as a function in Python and used it to find a target value, duplicates, and the largest value in different search lists. Let’s ...

- 1
Binary search is an efficient algorithm for finding values in a sorted data-set. Let's implement this algorithm in Python! Here's a recap of the algorithm:

***Check the middle value of the data... - 2
We now have a base case for when we do not find the value in our sorted list, but we need a base case for when we DO find the value. At this step, we have three options:

**BASE CASE:* - 3
With both of our base cases covered, we'll turn our attention to the recursive step. We have two options depending on the comparison of [...] to [...] . You'll recall that our data-set is sort...

- 4
Congratulations, you implemented a version of the binary search algorithm using recursion! Let's recap how we solved this problem: 1. We know our inputs will be sorted, which helps us make assert...

- 5
Anything recursive can be written iteratively. As a final exercise, we'll implement the binary search algorithm using iteration. Our strategy remains largely the same as the recursive approach w...

## How you'll master it

Stress-test your knowledge with quizzes that help commit syntax to memory