## Binary Search

This section covers Binary Search, which is an efficient algorithm for searching a sorted array for a target value.

We'll focus on how to visualize the algorithm, and how visualization can help us when we are implementing the algorithm. We'll then look at some practice questions involving Binary Search.

The classic Binary Search algorithm is used to search for a target value in a sorted array.

###### DESCRIPTION

Given a **sorted** array of integers nums and a target value target, write a function to determine if target is in the array. If target is present in the array, return its index. Otherwise, return -1.

**Example 1:**

Input:

```
nums = [-1,0,3,5,9,12], target = 9
```

Output: 4 (nums[4] = 9)

**Example 2:**

Input:

```
nums = [-1,0,3,5,9,12], target = 2
```

Output: -1 (2 is not in the array, so we return -1.)

The appeal of Binary Search is readily apparent when we compare it to the brute-force approach.

The graphic below shows how the brute-force approach searches the sorted array for the target value 6. The elements considered during the search are highlighted in darker color.

Compare that to Binary Search, which locates 6 after only 3 "steps":

These two graphics show the efficiency of Binary Search, which performs the search in O(log n) time, compared to the much slower O(n) time of the Brute-Force Approach.

### Intuition

Binary Search is efficient because it **repeatedly cuts the portion of the array that needs to be searched in half**.

Binary Search works because our array is sorted, and the middle element of a sorted array is a great starting point. All the elements to the left of the middle element are smaller than or equal to it, and all the elements to the right are larger than or equal to it.

Let's say our target is 6.

Since our **target is greater than the middle element, we can safely ignore the left half of the array** - we know the target is not there. We indicate this in the visual by turning those elements gray.

This leaves the right half of the array to search, and we've cut the search space in half for the first time.

How do we search the right half? With the same approach! We take the middle element of the right half (8), and compare it to the target.

Since our target is less than the middle element, we can now ignore the right half of the updated search space. We've just cut the search space in half again!

Now our search space has only two elements. By convention, we choose the first of these two elements as the "middle". Our target is equal to the middle element, meaning we've found it!

### Implementation

#### Variables

Before diving into the code, let's first learn what each variable represents in the Binary Search algorithm, and visualize how they change during the search.

For these visualizations, target = 6 and nums = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10].

- Initialize two pointers, left and right, to the start and end of the array, respectively.
**These two pointers represent the search space of the array**. Since the entire search space is valid, they are shown in green.

Next, we iteratively halve the search space until we've either found the target or the search space is empty (we will learn how to visualize this in the next section).

So while left <= right:

- Initialize a pointer mid = (left + right) // 2.
**mid represents the middle of the current search space**, as well as the element that we compare to target.

- Compare the element at mid to the target. In this case, target > nums[mid], so we
**drop the left half of the search space by updating left = mid + 1.**The elements that have been dropped are shown in gray.

At this point, left and right reflect the updated search space. So set mid = (left + right) // 2 again, and repeat the process until either nums[mid] == target or left > right.

target = 6

#### Code

Let's see the code!

def binary_search(nums, target):left = 0right = len(nums) - 1while left <= right:mid = (left + right) // 2if nums[mid] == target:return midif nums[mid] < target:left = mid + 1else:right = mid - 1return -1

#### Edge Cases

To deepen our understanding of Binary Search, let's consider some edge cases:

##### Empty Array

If the input array is empty, left starts at 0, right starts at -1, and the loop will not run, and we will return -1.

target = 2, nums = []

def binary_search(nums, target):left = 0right = len(nums) - 1while left <= right:mid = (left + right) // 2if nums[mid] == target:return midif nums[mid] < target:left = mid + 1else:right = mid - 1return -1

##### Single Element Array

If the input array has only one element, left, mid, and right will all be the same, and the loop will run once. If the single element is the target, we return its index. Otherwise, left > right, so we exit the loop and return -1.

target = 2, nums = [1]

def binary_search(nums, target):left = 0right = len(nums) - 1while left <= right:mid = (left + right) // 2if nums[mid] == target:return midif nums[mid] < target:left = mid + 1else:right = mid - 1return -1

##### Target Not in Array

If the target is not in the array, left will eventually be greater than right, and we will return -1.

target = 2, nums = [1, 3, 4, 8]

def binary_search(nums, target):left = 0right = len(nums) - 1while left <= right:mid = (left + right) // 2if nums[mid] == target:return midif nums[mid] < target:left = mid + 1else:right = mid - 1return -1

This example helps us visualize the **termination condition** of Binary Search.

When left = right, as shown below, there is still one element in the search space, highlighted in green.

However, when left > right, as shown below, the search space is empty, and we know that the target is not in the array. We can visualize the **binary search algorithm stopping when the left pointer "passes" the right pointer**.

These visualizations should help you internalize why the condition left <= right is used in the Binary Search algorithm - once left overtakes right, the search space is empty and we know that the target is not in the array.

### Complexity Analysis

**Time Complexity**: O(log n), since we are halving the search space at each step. n is the number of elements in the input array.

**Space Complexity**: O(1), since we are using a constant amount of space for the pointers, regardless of the size of the input array.

### Summary

Binary Search is an effective algorithm because it **allows us to repeatedly cut our search space in half until we find the target or conclude that it is not in the array**. In other words, during each iteration of the algorithm, we are able to discard half of the search space.

Here are some problems that also use this concept of repeatedly discarding half of the search space:

Question | Difficulty |
---|---|

Apple Harvest (Koko Eating Bananas) | Medium |

Search in Rotated Sorted Array | Medium |

Loading comments...