# Binary Search (Leetcode #704)

[Given an array of integers `nums` which](https://leetcode.com/problems/binary-search/) is sorted in ascending order, and an integer `target`, write a function to search `target` in `nums`. If `target` exists, then return its index. Otherwise, return `-1`.

You must write an a[lgorithm with `O(lo`](https://leetcode.com/problems/binary-search/)`g n)` runtime complexity.

**Example 1:**

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

**Example 2:**

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

**Constraints:**

* [`1 <= nums.length <= 10<sup>4</sup>`](https://leetcode.com/problems/binary-search/)
    
* [`-10<sup>4</sup> < num`](https://leetcode.com/problems/binary-search/)`s[i], tar`[`get < 10<sup>4</sup>`](https://leetcode.com/problems/binary-search/)
    
* [All t](https://leetcode.com/problems/binary-search/)he integers in [`nums` are **unique**.](https://leetcode.com/problems/binary-search/)
    
* `nums` is sorted in a[scending order.](https://leetcode.com/problems/binary-search/)
    

### Answer

The main clue of this question is that we have to solve it in a time complexity of O(long). This means we have to solve it using binary search.

**Binary Search**

A binary search is an efficient algorithm used to find a target value within a sorted array by repeatedly dividing the search range in half. It compares the target value to the middle element of the array and adjusts the search range to either the left or right half based on this comparison. This process continues until the target is found or the search range is exhausted, resulting in a time complexity of O(log n).

Here's the code

```python
class Solution(object):
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: 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
```

Most of the code is quite self-explanatory. However, there is one area I would like to focus on: the updates `l = mid + 1` and `r = mid - 1`.

When I first solved this question, I wondered why we couldn't just use `l = mid` or `r = mid` since the potential time saved here is very small.

To answer this question, I would like to give an example:

**Initial setup:**

`l = 0`, `r = 4` (indices of the array `nums`)

Array: `[1, 2, 3, 4, 5]`

Target: `6`

**First iteration:**

Calculate `mid`: `mid = (0 + 4) // 2 = 2`

Check `nums[mid]`: `nums[2] = 3`

Since `nums[2] < 6`, update `l` to `mid` (incorrect update).

New boundaries:

`l = 2`

`r = 4`

**Second iteration:**

Calculate `mid`: `mid = (2 + 4) // 2 = 3`

Check `nums[mid]`: `nums[3] = 4`

Since `nums[3] < 6`, update `l` to `mid` (incorrect update).

New boundaries:

`l = 3`

`r = 4`

**Third iteration:**

Calculate `mid`: `mid = (3 + 4) // 2 = 3`

Check `nums[mid]`: `nums[3] = 4`

Since `nums[3] < 6`, update `l` to `mid` (incorrect update).

New boundaries:

`l = 3`

`r = 4`

Hence, we are now stuck in an infinite loop. So when you are doing a binary search, remember to add or subtract 1 when updating the left and right boundaries.

**Time complexity:**

Since this is a binary search question we know that the time complexity is O(long)

since we are cutting the input by half each time

**Space complexity:**

O(1) since we are only storing pointer and nothing else