# Week 2: Binary Search

In a sorted list, binary search is a good method to search for an item. Each time we pick a “middle element”, and compare it to our target. If it is smaller than the target, then we keep doing binary search on its right side; if it is larger than the target, then we keep doing binary search on its left side. Note that each time we can get rid of about half of the list, so eventually it is an $O(\log n)$ algorithm. If you encounter an interview question asking you to implement an $O(\log n)$ algorithm, most likely it is asking for a binary search. Let’s start from the most classical question on binary search:

## Classical Binary Search Question:

Take a look at LeetCode #704:

LeetCode #704. Binary Search

Given a sorted (in ascending order) integer array `nums` of `n` elements and a `target` value, write a function to search `target` in `nums`. If `target` exists, then return its index, otherwise return `-1`.

Example 1:

```Input: `nums` = [-1,0,3,5,9,12], `target` = 9
Output: 4
Explanation: 9 exists in `nums` and its index is 4

```

Example 2:

```Input: `nums` = [-1,0,3,5,9,12], `target` = 2
Output: -1
Explanation: 2 does not exist in `nums` so return -1
```

Note:

1. You may assume that all elements in `nums` are unique.
2. `n` will be in the range `[1, 10000]`.
3. The value of each element in `nums` will be in the range `[-9999, 9999]`.

In this case, using the classical version of binary search is perfectly fine:

```class Solution:
def search(self, nums: List[int], target: int) -> int:
start = 0
end = len(nums) - 1
found = False

mid = (start + end) // 2
if nums[mid] == target:
return mid
else:
if target < nums[mid]:
end = mid - 1
else:
start = mid + 1

return -1```

However, for other types of questions, this version of binary search might not work. For example, let’s take a look at the next question:

## When Classical Version doesn’t work:

Take a look at Leetcode #34:

LeetCode #34. Find First and Last Position of Element in Sorted Array

Given an array of integers `nums` sorted in ascending order, find the starting and ending position of a given `target`value.

Your algorithm’s runtime complexity must be in the order of O(log n).

If the target is not found in the array, return `[-1, -1]`.

Example 1:

```Input: nums = [`5,7,7,8,8,10]`, target = 8
Output: [3,4]```

Example 2:

`Input: nums = [`5,7,7,8,8,10]`, target = 6 Output: [-1,-1]`

Very likely your first attempt would fail, and it is extremely frustrating to debug. The while loop can easily become an infinite loop, and that will give you a “Time Limit Exceeded” error. To fix this, let’s use the following template.

## A Better Binary Search Template:

This template code comes from here. Let’s see what is different:

```class Solution:
# @param nums: The integer array
# @param target: Target number to find
# @return the first position of target in nums, position start from 0
def binarySearch(self, nums, target):
if len(nums) == 0:
return -1

start, end = 0, len(nums) - 1

while start + 1 < end:
mid = (start + end) // 2
if nums[mid] < target:
start = mid
elif nums[mid] == target:
end = mid
else:
end = mid

if nums[start] == target:
return start
if nums[end] == target:
return end

return -1```

There are two major points that make this code a nice template:

1. We want to use `while start + 1 < end` for the while loop. This is because `start < end` and `start <= end` may give us infinite loop when finding the last position of target. Consider the following case:

`Input: nums = `[1, 1]`, target = `1` Output: `[0,1]``

If we write `start < end`, note that here we will have `start = 0` all the time as the loop goes. This makes `while start < end` or `while start <= end` always evaluate to `True`, and thus gives us an infinite loop. Using `while start + 1 < end` helps to get rid of any potential error.

2. We want to use `start = mid` and `end = mid`, instead of `start = mid + 1` and `end = mid - 1`. In some special cases, such as finding the last position of target, when `target == nums[mid]`, we can’t write `+1` and `-1`, for that we may miss some solutions. So for simplicity, just write `start = mid` and `end = mid` for any binary search question. This makes the algorithm $O(\log(n+1))$, which doesn’t make much difference as the standard $O(\log n)$.

## Solution to LeetCode #34:

Here is a solution to LeetCode #34 using above template:

```class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
return [self.first_position(nums, target), self.last_position(nums, target)]

def first_position(self, nums, target):
if len(nums) == 0:
return -1

start, end = 0, len(nums) - 1

while start + 1 < end:
mid = (start + end) // 2
if nums[mid] < target:
start = mid
elif nums[mid] == target:
end = mid
else:
end = mid

if nums[start] == target:
return start
elif nums[end] == target:
return end
else:
return -1

def last_position(self, nums, target):
if len(nums) == 0:
return -1

start, end = 0, len(nums) - 1

while start + 1 < end:
mid = (start + end) // 2
if nums[mid] < target:
start = mid
elif nums[mid] == target:
start = mid
else:
end = mid

if nums[end] == target:
return end
elif nums[start] == target:
return start
else:
return -1```

The only two differences between `first_position` and `last_position:`

1. When `nums[mid] == target`, `first_position` sets `end = mid` and `last_position` sets `start = mid`. This is very intuitive. For example, in `first_position`, you can’t just return `mid` when you find the target. You should set `end` to `mid`, so that you can keep searching the elements before it, just to see if the target occurs anywhere before the element you are looking at. Similar reasoning holds for `last_position`, too.
2. After the while loop, `first_position` checks `nums[start]` first, and `last_position` checks `nums[end]` first, for very obvious reason.

## Some Examples:

Using the template, binary search questions can be really easy to solve. For example, consider this question:

LeetCode #162. Find Peak Element

A peak element is an element that is greater than its neighbors.

Given an input array `nums`, where `nums[i] ≠ nums[i+1]`, find a peak element and return its index.

The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.

You may imagine that `nums[-1] = nums[n] = -∞`.

Example 1:

```Input: nums = `[1,2,3,1]`
Output: 2
Explanation: 3 is a peak element and your function should return the index number 2.```

Example 2:

```Input: nums = `[`1,2,1,3,5,6,4]
Output: 1 or 5
Explanation: Your function can return either index number 1 where the peak element is 2,
or index number 5 where the peak element is 6.
```

Note:

Your solution should be in logarithmic complexity.

Solution:

```class Solution:
def findPeakElement(self, nums: List[int]) -> int:
if len(nums) == 0:
return -1
if len(nums) == 1:
return 0

start, end = 0, len(nums) - 1

while start + 1 < end:
mid = (start + end) // 2
if nums[mid] > nums[mid + 1]:
end = mid
else:
start = mid

if nums[start] > nums[end]:
return start
elif nums[start] < nums[end]:
return end
else:
return -1```