Binary Search

TCS NQT Coding Easy Go Ad-Free - ₹20/mo

Given an array of integers nums sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, 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.

Input: nums = [5], target = 5

Output: 0

Explanation: 5 exists in nums and its index is 0.

Constraints

1 ≤ nums.length ≤ 10⁴
-10⁴ ≤ nums[i] ≤ 10⁴
All values in nums are unique
nums is sorted in ascending order
-10⁴ ≤ target ≤ 10⁴

Editorial

Intuition:

Since the array is sorted, binary search efficiently halves the search space each iteration by comparing the middle element with the target. This guarantees O(log n) time complexity.

Approach:

Initialize two pointers: left at index 0 and right at the last index (nums.length - 1).
While left <= right:
- Compute mid = left + (right - left) / 2 (avoids overflow).
- If nums[mid] == target, return mid.
- If nums[mid] < target, set left = mid + 1.
- Otherwise, set right = mid - 1.
If the loop ends, return -1 (target not found).

class Solution {
public:
    int search(const vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) return mid;
            else if (nums[mid] < target) left = mid + 1;
            else right = mid - 1;
        }
        return -1;
    }
};
class Solution {
    public int search(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) return mid;
            else if (nums[mid] < target) left = mid + 1;
            else right = mid - 1;
        }
        return -1;
    }
}
class Solution:
    def search(self, nums, target):
        left, right = 0, len(nums) - 1
        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] == target:
                return mid
            elif nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
        return -1
class Solution {
    search(nums, target) {
        let left = 0, right = nums.length - 1;
        while (left <= right) {
            let mid = left + Math.floor((right - left) / 2);
            if (nums[mid] === target) return mid;
            else if (nums[mid] < target) left = mid + 1;
            else right = mid - 1;
        }
        return -1;
    }
}

Complexity Analysis:

Time Complexity: O(log n), because the search space is halved in each iteration.

Space Complexity: O(1), as only a constant number of variables are used.

Notes

Your notes are automatically saved in your browser's local storage and will persist across sessions on this device.

Problem Categories