---
# System prepended metadata

title: '[Binary Search](https://leetcode.com/problems/binary-search/)'
tags: [Leetcode, Easy, Binary Search]

---

# [Binary Search](https://leetcode.com/problems/binary-search/)
###### tags: `Leetcode`, `Easy`, `Binary Search`

## Approach
![](https://i.imgur.com/KC2oc7F.png)

* Initialize two pointers `left` and `right`. `left` points to the first index value of the input list and `right` points to the last index value of the input list
* Keep looping as long as `left <= right`
* Calculate `mid = (left + right) / 2`. 
    * If `mid == target` then return mid
    * If `nums[mid] < target` then `left = mid + 1`
    * If `nums[mid] > target` then `right = mid - 1`
* If loop is over and target was not found then return `-1`

## Asymptotic Analysis
### Time Complexity: **O(log N)**
### Space Complexity: **O(1)**

## Code
``` python
from typing import List


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


numbers, target = [-1, 0, 3, 5, 9, 12], 9
print("Index of the target: " + str(BinarySearch().search(numbers, target)))
```