### View *Binary Search* on LeetCode

## Statistics

**Time Spent Coding**

1 minute

**Time Complexity**

O(log n) - The binary search algorithm takes at most O(log n) time.

**Space Complexity**

O(1) - The number of variables created is independent of the input list, resulting in the O(1) space complexity.

## Explanation

To set up a binary search, you must always create a left `l`

and a right `r`

pointer. The left pointer points at the minimum value and the right points at the maximum; in this problem, it would be the max/min indices.

Repeatedly search until the left pointer exceeds the right.

The middle pointer is initialized with the middle value between the left and right pointers.

Then check two conditions:

- If the value at the middle index is the target,
`return mid`

- If the value is less than the target, it is impossible for the target to be in the left portion of the list; this is known because the left portion is always smaller than the value at the middle index. Therefore, the left pointer is updated to the middle index + 1.
- If neither of these conditions are true, then the value at the middle is greater than the target. Therefore, the right pointer is updated to the middle index - 1, for the inverse reason as the last condition.

If the `while`

loop exists, the target is not within the input list.

## Algorithm Used

**Binary Search -** A search algorithm that repeatedly halves the search interval until the target variable is found at the middle index.

**Visual Examples**

Binary search being performed on an array that contains the target, click to view

Binary search being performed on an array that does **not** contain the target, click to view

## Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution:
def search(self, nums: List[int], target: int) -> int:
l = 0
r = len(nums) - 1
while l <= r:
mid = (l+r)//2
if nums[mid] == target:
return mid
elif nums[mid] < target:
l = mid + 1
else:
r = mid - 1
return -1