When working with arrays, you’ll often have to search through them to check if they contain a target element.

You can always run a sequential search—scanning the array from the beginning to the end—on the array. But if the array is sorted, running the binary search algorithm is much more efficient.

Let's learn how binary search works, its time complexity, and code a simple implementation in Python.

## How Does Linear Search Work?

We'll start our discussion with **linear **or** sequential search**.

Suppose we have an unsorted sequence of numbers `nums`

. Given this nums array, you should check if the `target`

is present in `nums`

. You don’t have information about whether `nums`

is sorted.

So the only way you can do this is to scan the array in a linear fashion, starting at the first element—until you find a match.

You can loop through the entire array to check if the element at index `i`

matches the `target`

. Once you find a match, you can break out of the loop.

Notice that in the worst case, you’ll have to scan the entire array and be lucky enough to find a match at the last index. Or you’ll have exhausted the array—without finding a match—indicating that the element is not present in the array.

Suppose the array has `n`

elements. Because you have to scan the entire array—in the worst case—the linear search algorithm has a time complexity of O(n).

Here's an example:

But when you do not know anything about the sequence, this is the best you can do. *So linear or sequential search is the best you can do when searching through unsorted sequences.*

### How Linear Search Works in Python

The function `linear_search`

takes in an array `nums`

and a `target`

to search for. It then loops through the array sequentially to check if `target`

is present in `nums`

:

```
def linear_search(nums,target):
for num in nums:
if num == target:
return True
return False
```

Here are a couple of sample outputs:

```
nums = [14,21,27,30,36,2,5,7,11]
target = 27
print(linear_search(nums,target))
# Output: True
target = 100
print(linear_search(nums,target))
# Output: False
```

## How Does Binary Search Work?

Now consider the `nums`

sequence with `n`

elements sorted in ascending order. For any valid index `k`

, the following holds `True`

for the element `a_k`

at index `k`

:

The elements at indices 0, 1, 2, …, (k-1) are all less than or equal to`a_k`

. And all elements at indices (k+1) to (n-1) are greater than or equal to`a_k`

.

With this information, you no longer need to run a linear scan. You can do it much faster with binary search.

We’re given a sorted array `nums`

and a `target`

. Let mid denote the middle-most index of the array and `nums[mid]`

denote the element at the middle index. Here’s how the binary search algorithm works:

- Check if
`nums[mid]`

is equal to the`target`

. If so, we’ve already found a match—in the very first step—and the search terminates. - If
`nums[mid]`

>`target`

, you*only*need to search the*left half*of the array. Even when you search through the left subarray you can use the same binary search algorithm. - If
`nums[mid]`

<`target`

, you can ignore all the elements up to the middle element and*only*consider the*right half*of the array.

Notice that we have a recurrence relation here. First, we start by running the binary search algorithm on the array with n elements. If we don't find the target in the very first step, we run binary search on the subarray of size at most n/2 elements.

If we end up with an empty array or an array with one element that is *not* the `target`

, we conclude that the target does not exist in the `nums`

array.

### How to Implement Binary Search in Python

Here's a recursive implementation of binary search in Python:

```
def binary_search(nums,target,low,high):
if low > high:
return False
else:
mid = (low + high)//2
if nums[mid] == target:
return True
elif nums[mid] < target:
return binary_search(nums,target,mid+1,high)
else:
return binary_search(nums,target,low,mid-1)
```

With a few sample runs of the `binary_search`

function:

```
nums = [2,5,7,11,14,21,27,30,36]
target = 27
print(binary_search(nums,target,0,len(nums)-1))
# Output: True
target = 38
print(binary_search(nums,target,0,len(nums)-1))
# Output: False
```

## What Is the Time Complexity of Binary Search?

In binary search, we know that the *search space is reduced by half* at each step and this guides us in computing the time complexity.

For an array with `n`

elements, we check if the middle-most element matches the `target`

. If so, we return `True`

and terminate the search.

But if the middle element does not match the `target`

, we perform binary search on a subarray of size at most `n/2`

. In the next step, we have to search through an array of size at most `n/4`

. And we continue this recursively until we can make a decision in a constant time (when the subarray is empty).

At step `k`

, we need to search through an array of size at most `n/(2^k)`

. And we need to find the smallest such `k`

for which we have no subarray to search through.

Mathematically:

The time complexity of binary search is, therefore, **O(logn)**. This is much more efficient than the linear time O(n), especially for large values of n.

For example, if the array has 1000 elements. 2^(10) = 1024. While the binary search algorithm will terminate in around 10 steps, linear search will take a thousand steps in the worst case.

## Wrapping Up

And that's a wrap. I hope you found this introduction to binary search helpful! You’ll often run into questions involving binary search in coding interviews.

If you’re preparing for coding interviews, check out 10 Common Coding Interview Questions [Solved] on freeCodeCamp’s YouTube channel.