# Binary Search (#704)

##### Problem Statement

Complexity: Easy

Given an array of integers `nums` which 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 algorithm with `O(log n)` runtime complexity.

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```

Constraints:

• `1 <= nums.length <= 104`
• `-104 < nums[i], target < 104`
• All the integers in `nums` are unique.
• `nums` is sorted in ascending order.

##### Solution Explanation:
###### References:

To achieve a time complexity of O(log n), we can use binary search algorithm.

The idea of binary search is to divide the search space in half at each step. We start by setting two pointers, ‘`left`‘ and `'right`‘, to the beginning and end of the array, respectively. We then calculate the midpoint of the search space as `mid = ``'(left + right) // 2`.

We compare the value at the midpoint `nums'[mid]'` with the target value. If they are equal, we have found the target and return its index `mid`. If ‘`nums[mid] < target`‘, we know that the target must be in the right half of the search space, so we move the `left` pointer to ‘`mid + 1`‘. Otherwise, we move the `right` pointer to `mid - 1`‘.

We repeat this process until we find the target or the search space is empty, which is when ‘`left > right`‘. If we don’t find the target by then, we return `-1`.

The time complexity of this algorithm is O(log n) because we divide the search space in half at each step, which reduces the search space exponentially.

Let’s understand it with an example:

We have a sorted array: [1, 3, 4, 6, 8, 9, 11], and we need to find 4 in it.

We’d initialise the pointers to extreme ends of array, i.e., left pointer to 0 and right pointer to 1.

Then, we’ll find the middle element, the middle element is `6`.

`mid = (left + right) // 2 = (0 + 6) // 2 = 3`

Since the middle element is greater than the target, the target must be in the left half of the search range.

We’ll repeat the process until we find the solution or dataset is empty.

##### Solution Code:
###### Solution 1

By using ‘enumerate‘. It is a built-in Python function that returns an iterator of tuples containing indices and values from an iterable.

``````class Solution:
def search(self, nums: List[int], target: int) -> int:
for indx, num in enumerate(nums):
if num == target:
return indx
return -1``````
###### Solution 2

Using binary search, where we divide the sorted array in half repeatedly until the target element is found, or the search space is empty

``````class Solution:
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
elif nums[mid] < target:
left = mid + 1
else:
right = mid - 1

return -1``````
Scroll to Top