LeetCode · #704

Binary Search Solution

Given a sorted array nums and a target, return the index of target or -1 if not found.

Section One · Problem

Problem Statement

🏷️

Difficulty

Easy

🔗

LeetCode

Problem #704

🏗️

Pattern

Binary Search — classic

Given a sorted (ascending) integer array nums of n elements and an integer target, write a function to search target in nums. If target exists, return its index. Otherwise return -1.

Example

 Input: nums = [-1,0,3,5,9,12], target = 9 Output: 4 // 9 exists in nums at index 4 

Constraints

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

Section Two · Approach 1

Linear Scan — O(n)

Walk through every element and check if it equals the target. Correct but ignores the sorted property.

Problem: O(n) scan wastes the sorted guarantee. Binary search halves the search space each step for O(log n).

Java — Linear Scan

 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 — Linear Scan

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

Metric	Value
Time	O(n)
Space	O(1)

Section Three · Approach 2

Binary Search — O(log n)

Maintain two pointers left and right. Compute mid. If nums[mid] == target, return mid. If target is smaller, search the left half. If larger, search the right half. Repeat until found or search space is empty.

💡 Mental model: Think of looking up a word in a dictionary. You don't start at page 1 — you open to the middle. If your word comes before, you flip to the left half's middle. Each flip eliminates half the remaining pages. After ~17 flips you've found any word among 100,000 pages.

Algorithm

Step 1: left = 0, right = n - 1.
Step 2: While left ≤ right: compute mid = left + (right - left) / 2.
Step 3: If nums[mid] == target → return mid.
Step 4: If nums[mid] < target → left = mid + 1.
Step 5: If nums[mid] > target → right = mid - 1.
Step 6: If loop ends → return -1.

🎯 Why left + (right - left) / 2?:

Avoids integer overflow that (left + right) / 2 can cause when both are large.
In Python this isn't an issue (arbitrary precision), but it's a best practice in Java/C++.

Section Four · Trace

Visual Walkthrough

Trace through nums = [-1, 0, 3, 5, 9, 12], target = 9:

Binary Search — halve the search space each step

Section Five · Implementation

Code — Java & Python

Java — Binary Search

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

Python — Binary Search

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

Section Six · Analysis

Complexity Analysis

Approach	Time	Space	Trade-off
Linear Scan	O(n)	O(1)	Ignores sorted property
Binary Search ← optimal	O(log n)	O(1)	Halves search space each step

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	Input	Why It Matters
Single element	`[5], target=5`	L==R==mid==0. Found immediately.
Not found	`[1,3,5], target=4`	L crosses R → return -1.
Target at start	`[1,2,3], target=1`	mid goes left → found at index 0.
Target at end	`[1,2,3], target=3`	mid goes right → found at last index.

⚠ Common Mistake: Using left < right instead of left <= right. With strict <, the case where the target is at the last remaining position (L==R) is skipped, causing a miss. Always use ≤ for standard find-target binary search.

← Back to Binary Search problems

LearningTree

LC 704 · Binary Search — Solution & Explanation | DSA Guide