# Linear & Binary Search

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

Start## Key Concepts

Review core concepts you need to learn to master this subject

Linear search

Linear Search Complexity

Linear Search best case

Linear Search expressed as a Function

Return value of a linear search

Linear search as a part of complex searching problems

Modification of linear search function

Searching for smallest or largest value using linear search

Linear search

Linear search

*Linear search* sequentially checks each element of a given list for the target value until a match is found. If no match is found, a linear search would perform the search on all of the items in the list.

For instance, if there are `n`

number of items in a list, and the target value resides in the `n-5`

th position, a linear search will check `n-5`

items total.

Linear Search Complexity

Linear Search Complexity

Linear search runs in linear time and makes a maximum of `n`

comparisons, where `n`

is the length of the list. Hence, the computational complexity for linear search is O(N).

The running time increases, at most, linearly with the size of the items present in the list.

Linear Search best case

Linear Search best case

For a list that contains `n`

items, the best case for a linear search is when the target value is equal to the first element of the list. In such cases, only one comparison is needed. Therefore, the best case performance is O(1).

Linear Search expressed as a Function

Linear Search expressed as a Function

A linear search can be expressed as a function that compares each item of the passed dataset with the target value until a match is found.

The given JavaScript code block demonstrates a function that performs a linear search. The relevant index is returned if the target is found and -1 if it is not.

Return value of a linear search

Return value of a linear search

A function that performs a linear search can return a message of success and the index of the matched value if the search can successfully match the target with an element of the dataset. In the event of a failure, an indication is returned as well.

For instance, in the given code block, the index `i`

will be returned if a value is matched with the target. The value `-1`

will be returned if there was no match.

Linear search as a part of complex searching problems

Linear search as a part of complex searching problems

Despite being a very simple search algorithm, linear search can be used as a subroutine for many complex searching problems. Hence, it is convenient to implement linear search as a function so that it can be reused.

Modification of linear search function

Modification of linear search function

A linear search can be modified so that all instances in which the target is found are returned. This change can be made by not ‘breaking’ when a match is found.

Searching for smallest or largest value using linear search

Searching for smallest or largest value using linear search

Linear search can be used to search for the smallest or largest value in an unsorted list rather than searching for a match. It can do so by keeping track of the largest (or smallest) value and updating as necessary as the algorithm iterates through the dataset.

Linear Search Best and Worst Cases

Linear Search Best and Worst Cases

The best-case performance for the Linear Search algorithm is when the search item appears at the beginning of the list and is O(1). The worst-case performance is when the search item appears at the end of the list or not at all. This would require N comparisons, hence, the worse case is O(N).

Linear Search Average Runtime

Linear Search Average Runtime

The Linear Search Algorithm performance runtime varies according to the item being searched. On average, this algorithm has a Big-O runtime of O(N), even though the average number of comparisons for a search that runs only halfway through the list is N/2.

Linear Search Runtime

Linear Search Runtime

The Linear Search algorithm has a Big-O (worst case) runtime of O(N). This means that as the input size increases, the speed of the performance decreases linearly. This makes the algorithm not efficient to use for large data inputs.

Binary Search

Binary Search

Binary search performs the search for the target within a sorted array. Hence, to run a binary search on a dataset, it must be sorted prior to performing it.

Operation of a Binary Search

Operation of a Binary Search

The binary search starts the process by comparing the middle element of a sorted dataset with the target value for a match. If the middle element is equal to the target value, then the algorithm is complete. Otherwise, the half in which the target cannot logically exist is eliminated and the search continues on the remaining half in the same manner.

The decision of discarding one half is achievable since the dataset is sorted.

Complexity of Binary Search

Complexity of Binary Search

A dataset of length n can be divided *log n* times until everything is completely divided. Therefore, the search complexity of binary search is O(log n).

Updating pointers in a recursive binary search

Updating pointers in a recursive binary search

In a recursive binary search, if the value has not been found then the recursion must continue on the list by updating the left and right pointers after comparing the target value to the middle value.

If the target is less than the middle value, you know the target has to be somewhere on the left, so, the right pointer must be updated with the middle index. The left pointer will remain the same. Otherwise, the left pointer must be updated with the middle index while the right pointer remains the same. The given code block is a part of a function `binarySearchRecursive()`

.

Iterative Binary Search

Iterative Binary Search

A binary search can be performed in an iterative approach. Unlike calling a function within the function in a recursion, this approach uses a loop.

Binary Search

Binary Search

The binary search algorithm efficiently finds a goal element in a sorted dataset. The algorithm repeatedly compares the goal with the value in the middle of a subset of the dataset. The process begins with the whole dataset; if the goal is smaller than the middle element, the algorithm repeats the process on the smaller (left) half of the dataset. If the goal is larger than the middle element, the algorithm repeats the process on the larger (right) half of the dataset. This continues until the goal is reached or there are no more values.

Binary Search Performance

Binary Search Performance

The binary search algorithm takes time to complete, indicated by its `time complexity`

. The worst-case time complexity is `O(log N)`

. This means that as the number of values in a dataset increases, the performance time of the algorithm (the number of comparisons) increases as a function of the base-2 logarithm of the number of values.

Example: Binary searching a list of 64 elements takes at MOST `log2(64)`

= 6 comparisons to complete.

Throwing Exception in Linear Search

Throwing Exception in Linear Search

The linear search function may throw a `ValueError`

with a message when the target value is not found in the search list. Calling the linear search function inside a `try`

block is recommended to catch the `ValueError`

exception in the `except`

block.

Raise Error in Linear Search

Raise Error in Linear Search

A Linear Search function accepts two parameters:

```
1) input list to search from
2) target element to search for in the input list
```

If the target element is found in the list, the function returns the element index. If it is not found, the function raises an error. When implementing in Python, use the `raise`

keyword with `ValueError()`

.

Linear Search Multiple Matches

Linear Search Multiple Matches

A linear search function may have more than one match from the input list. Instead of returning just one index to the matched element, we return a list of indices. Every time we encounter a match, we add the index to the list.

Find Maximum Value in Linear Search

Find Maximum Value in Linear Search

The Linear Search function can be enhanced to find and return the maximum value in a list of numeric elements. This is done by maintaining a variable that is compared to every element and updated when its value is smaller than the current element.

Recursive Binary Search

Recursive Binary Search

Binary search can be implemented using recursion by creating a function that takes in the following arguments: a sorted list, a left pointer, a right pointer, and a target.

The base cases must account for when the left and right pointers are equal, as well as when the target is found, in which case the the index of the array is returned.

Initially, set the left pointer to index 0 of the list and right pointer to the last index. If middle value > target, right pointer = middle value. If middle value < target, left pointer = middle value. Call the binary search function with the properly adjusted pointers.

- 1Imagine 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 …
- 2Linear 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…
- 3Linear 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…
- 4There 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+… - 5If this search was used 1000 times on 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 the…
- 6Linear 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…

- 1With 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…
- 2Play with this interactive visualization demonstrating binary search. Refresh the page to play again with a different list.
- 3How efficient is binary search? In each iteration, we are
**cutting the list in half.**The time complexity is O(log N). A sorted list of 64 elements will take**at most**log 2 (64) = 6 compari…

- 1The
*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… - 2Linear 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…
- 3In the text editor, you will find the code for the linear_search() function that we implemented in Python. When called, our function returns either an index of an element that matches the target …
- 4With a few changes to our code, we can modify linear search to solve more complex search problems. Our linear search function, linear_search(), currently finds whether one given value exists in a …
- 5The 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…
- 6You 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 …

- 1Binary 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…
- 2We 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:**mid_val … - 3With both of our base cases covered, we’ll turn our attention to the recursive step. We have two options depending on the comparison of mid_val to target. You’ll recall that our data-set is sorte…
- 4Congratulations, 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…
- 5Anything 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