Binary Search

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.

Example 1:
Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4

Example 2: Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1

Constraints:

• 1 <= nums.length <= 10⁴
• -10^{4 <= nums[i] <= 104}
• All the integers in nums are unique.
• nums is sorted in ascending order.

Approach I

First approach is an iterative where while look is used to sort through the list.

Complexity for this method is O(logN) since we halve the length of list with each iteration.

Solution

def binarySearch(nums, target):
    start = 0
    end = len(nums)-1

    while start <= end:
        mid = start + (end- start)/2
        if nums[mid] == target:
            return mid
        
        elif nums[mid] < target:
            end = mid-1
        
        else:
            start = mid+1
    return -1

Approach II

In second approach, we use recusion to write binary search function.

Complexity: Time complexity is O(logn), space complexity is O(1).

Solution

def binarySearch(nums,start, end, target):
    if start <= end:
        # to avoid overflow
        mid = start + (end-start)//2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            return binarySearch(nums, mid+1, end, target)
        else:
            return binarySearch(nums, start, mid-1, target)
    
    return -1

Refrence

• FlyKiller