# #704 - Binary Search - LeetCode

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.

## Problem Statement

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.

## Examples

```
Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Explanation: 9 exists in nums and its index is 4
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`

^{4}`-10`

^{4}< nums[i], target < 10^{4}- All the integers in
`nums`

are**unique**. `nums`

is sorted in an ascending order.

## Solution

This is quite straight forward. The problem states that we need to find the `target`

from a `sorted`

array `nums`

in `O(log n)`

time. Whenever you see that the array is sorted and that the expected time complexity is `O(log n)`

, the first thing that has to come to your mind is **Binary Search**.

Most importantly, this problem's title says binary search ðŸ˜‚ðŸ˜‚. So, just perform binary search on the array and return the index.

For those of you who don't know what binary search is, don't worry. At the end of this article I've linked an article from GeeksforGeeks, which should help you understand this algorithm.

### Python

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

In Python, we can use `mid = (low + high) // 2`

without any consequences, but in other programming languages like Java and C++, it is recommended that we use `mid = (low + (high - low)) // 2`

so as to avoid the plausible overflow error on doing `low + high`

.

This approach has a time complexity of `O(log n)`

and has a space complexity of `O(1)`

.

## References

- LeetCode Problem Link - Binary Search - LeetCode
- GeeksforGeeks article on Binary Search - Binary Search - GeeksforGeeks