Difficulty: Easy · LeetCode 704

Problem

Given an array of integers nums sorted in ascending order and a target integer target, write a function to search target in nums. Return index if present else -1.

Understanding the problem

Eliminate half of the remaining search space on each step in a sorted array.

Intuition

Use two pointers left and right. Calculate mid = left + (right - left) // 2. If nums[mid] == target return mid, else adjust boundaries.

Approach

Initialize left = 0, right = len(nums) - 1.
Loop while left <= right:
Compute mid = left + (right - left) // 2.
If nums[mid] == target, return mid.
If nums[mid] < target, set left = mid + 1.
Else, set right = mid - 1.
Return -1 if target not found.

Naive Solution — Brute Force

Scan every element linearly from index 0 to n-1.

Python

class Solution:
    def search(self, nums, target):
        for i, num in enumerate(nums):
            if num == target:
                return i

        return -1

C++

class Solution {
public:
    int search(vector<int>& nums, int target) {
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] == target) {
                return i;
            }
        }

        return -1;
    }
};

Java

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;
    }
}

JavaScript

var search = function(nums, target) {
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] === target) {
            return i;
        }
    }

    return -1;
};

Time: O(n) · Space: O(1)

Optimized Code (Python 3)

Python

class Solution:
    def search(self, nums, target):
        left = 0
        right = len(nums) - 1

        while left <= right:
            mid = left + (right - left) // 2

            if nums[mid] == target:
                return mid

            if nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1

        return -1

C++

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;

            if (nums[mid] == target) {
                return mid;
            }

            if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return -1;
    }
};

Java

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

        while (left <= right) {
            int mid = left + (right - left) / 2;

            if (nums[mid] == target) {
                return mid;
            }

            if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return -1;
    }
}

JavaScript

var search = function(nums, target) {
    let left = 0;
    let right = nums.length - 1;

    while (left <= right) {
        const mid = left + Math.floor((right - left) / 2);

        if (nums[mid] === target) {
            return mid;
        }

        if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return -1;
};

Time: O(log n) · Space: O(1)

Takeaway

Pattern — Sorted array → Eliminate half → Standard Binary Search