Day 27 — Binary Search | Blind75 | Java

Problem

Given a sorted array of unique integers and a target value, return the index of the target if it exists.

If the target does not exist, return -1.

The main requirement is:

Time Complexity: O(log n)

This makes Binary Search the optimal approach.

Approach 1: Brute Force

The simplest approach is to traverse the array from left to right.

For every element, check whether it is equal to the target.

If we find it, return its index.

Otherwise, after checking the complete array, return -1.

Code

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

Complexity

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

This solution works, but it doesn’t take advantage of the fact that the array is sorted.

That’s where Binary Search comes in.

Approach 2: Binary Search — Iterative

Since the array is sorted, we can eliminate half of the search space after every comparison.