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

Solution

Real Life Example (Binary Search)

When seeking the meaning of a word like 'Quench' in a dictionary, we typically flip to the middle of the book and quickly scan the words listed on the left side of the page. If we encounter words starting with the letter 'k', it indicates that our target word will be on the right side. Subsequently, we focus on the midsection of the right half and continue scanning. This outlines the process.

In binary search, it's crucial to consider the following:

• What constitutes our search space?

• Is our search space sorted?

Linear Search Approach

Before delving into binary search, it's essential to first consider linear search. This method allows us to effectively identify our search space. With this approach, we start from the initial index and proceed sequentially, checking each element to see if it matches our target element. If a match is found, we return the result.

class Solution {
    public int search(int[] nums, int target) {
        for(int i=0; i<nums.length; i++){
            if(nums[i]==target) return i;
        }
        return -1;
    }
}

Binary Search Approach

The provided code presents the standard algorithm applicable to problems utilizing the binary search approach. Initially, we set the 'low' pointer to 0 and the 'high' pointer to the index of the last element. We then determine the midpoint ('mid') and verify if it corresponds to the target element. If a match is found, we immediately return the index. Otherwise, we proceed with the subsequent steps.

In the following step, we compare the element at 'mid' with the target. If the target is greater than 'mid', we shift our search to the right half by advancing 'low' to 'mid + 1' and continuing the process. Conversely, if the target is less than 'mid', we explore the left half by adjusting 'high' to 'mid - 1'.

This entire process is encapsulated within a while loop, which iterates as long as the condition 'low <= high' holds true.

Iterative Approach (Recommended)

class Solution {
    public int search(int[] nums, int target) {
        int low = 0;
        int high = nums.length-1;

        while(low <= high){
            int mid = (low+high)/2;
            if(nums[mid]==target) return mid;

            if(nums[mid]<target) low = mid+1;
            else high = mid -1;
        }
        return -1;
    }
}

Recursive Approach

Like the iterative method, the key difference lies in invoking binary search once we establish the target's segment. Equally vital is the base case, where we confirm the search space's validity by ensuring that the 'low' and 'high' pointers have not overlapped.

class Solution {

    public int binarySearch(int[] nums, int target, int low, int high){
        if(low>high) return -1;

        int mid = (low+high)/2;
        if(nums[mid]==target) return mid;

        if(nums[mid]<target) 
            return binarySearch(nums, target, mid+1, high);

        return binarySearch(nums, target, low, mid-1);
    }

    public int search(int[] nums, int target) {

        for(int i=0; i<nums.length; i++){
            if(nums[i]==target) return i;
        }

        return -1;
    }
}

Time Complexity Analysis

Time - O(logn)

Space - O(1)

If the search space has n=32 elements then the maximum steps it takes to find out the target is 6.