Binary Search

Easy Problem 40 of 151 Java and Python

Problem

Given a sorted (ascending) array of distinct integers nums and an integer target, return the index of target, or -1 if it is not present.

Your algorithm must run in O(log n) time.

Example 1

Input: nums = [-1, 0, 3, 5, 9, 12], target = 9
Output: 4

Example 2

Input: nums = [-1, 0, 3, 5, 9, 12], target = 2
Output: -1

Constraints

1 ≤ nums.length ≤ 10⁴
All values are unique and sorted ascending.

Explanation

Look at the middle element. If it is too small, the target can only be on the right; if too big, only on the left. Each comparison throws away half the remaining elements.

Approach 1 · Naive

Linear scan

Time O(n)
Space O(1)

Check every element until you find the target.

For each index, return it if nums[i] == target.
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;
    }
}

Python

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        for i, num in enumerate(nums):
            if num == target:
                return i
        return -1

Approach 2 · Optimal

Binary search

Time O(log n)
Space O(1)

Keep a range [lo, hi] that must contain the target if it exists, and halve it every step.

Set lo = 0, hi = n - 1.
While lo <= hi: mid = lo + (hi - lo) / 2.
If nums[mid] == target, return mid; if smaller, lo = mid + 1; else hi = mid - 1.
Return -1.

Java

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

Python

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        lo, hi = 0, len(nums) - 1
        while lo <= hi:
            mid = (lo + hi) // 2
            if nums[mid] == target:
                return mid
            if nums[mid] < target:
                lo = mid + 1
            else:
                hi = mid - 1
        return -1

Complexity compared

Approach	Time	Space
Naive Linear scan	O(n)	O(1)
Optimal Binary search	O(log n)	O(1)

Key takeaways

Write lo + (hi - lo) / 2 in Java so lo + hi cannot overflow.
Decide up front whether hi is inclusive (lo <= hi) or exclusive (lo < hi), and stay consistent.

Your notes

Saved in this browser as you type.

Solved it on your own?

Mark it done to track your progress, or star it to come back before an interview.

Next problem