# [Leet Code] Binary Search

Leetcode: https://leetcode.com/problems/binary-search/

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:

class Solution(object):

def search(self, nums, target):

"""

:type nums: List[int]

:type target: int

:rtype: int

"""

high = len(nums)-1

low = 0

return self.binary_search(nums, target, high, low)

def binary_search(self, nums, target, high, low):

print("high", high)

print("low", low)

if high >= low:

middle = (high + low) // 2if target > nums[middle]:

return self.binary_search(nums, target, high, middle+1)

elif target < nums[middle]:

return self.binary_search(nums, target, middle-1, low)

else:

return middle

else:

return -1