#704 - Binary Search - LeetCode

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 <= 104
• -104 < nums[i], target < 104
• 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

1. LeetCode Problem Link - Binary Search - LeetCode
2. GeeksforGeeks article on Binary Search - Binary Search - GeeksforGeeks