Binary Search

Leetcode Daily Challenge (1st April, 2023)

1 April, 2023

Contributors

Lakshit Chiranjiv Sagar

@lakshit-cs

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.

Link: https://leetcode.com/problems/binary-search/description/

Problem Explanation with examples:-

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.

Intuition:-

Its a sorted array and the best search algo for sorted array is binary search.
Simply find the mid and check if its the target, if not, then reduce the search space by half depending on the target and mid value.

Solution:-

Initialize l and r to 0 and n-1 respectively.
While l <= r, find the mid by (l+r)//2.
If nums[mid] == target, return mid.
If nums[mid] > target, then reduce the search space by half by setting r = mid-1.
If nums[mid] < target, then reduce the search space by half by setting l = mid+1.
If the target is not found, return -1 after the while loop.

Code:-

JAVA Solution

class Solution {
    public int search(int[] nums, int target) {
        int s=0;
        int e=nums.length-1;
        int m = (s+e)/2;
        while(s<=e){
            m = (s+e)/2;
            if(nums[m] == target)
                return m;
            else if(nums[m] < target)
                s = m+1;
            else{
                e = m-1;
            }
        }
        return -1;
    }
}

Python Solution

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        n = len(nums)
        l = 0
        r = n-1
        
        while l <= r:
            m = (l+r)//2
            if nums[m] == target:
                return m
            elif nums[m] > target:
                r = m-1
            else:
                l = m+1

        return -1

Complexity Analysis:-

TIME:-

The time complexity is O(logn) where n is the length of the array nums as we are reducing the search space by half at every step.

SPACE:-

The space complexity is O(1) as we are not using any extra space.

References:-

Binary Search