# 704. Binary Search — LeetCode(Python)

I got you!

# Problem:

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:

`l, r = 0, 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

## Explanation:

The algorithm is pretty standard. We create two pointers on left and right ends of our array *nums.*

Then we calculate our array’s *mid* element.

If this index contains the target value, we return this index.

Since, we know that the *array is sorted,* we check if the target value is greater than the element we’re at. If yes, we check only the right subarray, which has larger values than ** nums[mid]. **We accomplish this by shifting our left pointer to the index after mid.

And if the target value is less than our current element, we only check the left subarray, which has smaller values than ** nums[mid]. **We accomplish this by shifting our right pointer to the index before mid.

If we don’t come across the target value in the array, we return -1.

## Time and Space Complexity:

We are dividing the array into equal halves on every iteration, until only a single number is left in the array, after which our termination ** l ≤ r **becomes

*False.*

And, we know, the number of times we can divide a number by two to reach one, is log2(n). [2 is the base]

We also note that we require a constant amount of extra space for our algorithm.

Thus, if *n* is the length of the array *nums,*

Time Complexity: O(log(n))

Space Complexity: O(1)