Linear & Binary Search

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

Start[missing "en.views.course_landing_page.search-algorithms.course_illustration" translation]
Chevron Left Icon
Linear Search: Conceptual
Lesson 1 of 4
Chevron Right Icon
  1. 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. 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. 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. 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. 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. 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. 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. 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. 2

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

  3. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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

Pro Logo

Linear & Binary Search

Start[missing "en.views.course_landing_page.search-algorithms.course_illustration" translation]