Binary Search
Problem link: https://leetcode.com/problems/binary-search
Problem Statement
Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.
Input
nums: A sorted array of integers.target: The value to locate.
Output
The index of target (integer) or -1 if not found.
Example
Input: nums = [-1,0,3,5,9,12], target = 9 Output: 4
Explanation
9 exists in nums and its index is 4.
Brute Force
Intuition
Check every element one by one from the start of the array until the target is found.
Approach
- Iterate from $i = 0$ to $n-1$.
- If
nums[i] == target, return $i$. - If loop finishes, return -1.
Dry Run
Searching for 9 in [-1,0,3,5,9,12]: Check -1... 0... 3... 5... 9 (Found at index 4).
Code (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;
}
}
Complexity Analysis
In the worst case, we might have to scan the entire array.
Optimal Solution
Intuition
Since the array is sorted, we can eliminate half of the search space in every step by comparing the target with the middle element.
Approach
- Initialize
low = 0andhigh = n - 1. - While
low <= high:- Find
mid = low + (high - low) / 2. - If
nums[mid] == target, returnmid. - If
nums[mid] < target, movelow = mid + 1. - Else, move
high = mid - 1.
- Find
- Return -1 if not found.
Visualization
Code (Java)
class Solution {
public int search(int[] nums, int target) {
int low = 0, high = nums.length - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (nums[mid] == target) return mid;
else if (nums[mid] < target) low = mid + 1;
else high = mid - 1;
}
return -1;
}
}
Complexity Analysis
The search space is halved in every iteration, leading to a logarithmic time complexity.
Quick Revision (Brute Force)
- Linear scan
- No sorting required
Quick Revision (Optimal)
- Sorted array required
- Divide and conquer
- Avoid overflow with low + (high-low)/2