Clean Code Studio
LeetCode Practice Problems for each Binary Search Implementation and Variation Linked Below
- Mastering Binary Search
Variations of Binary Search (patterns to practice)
Worth knocking these into muscle memory
1. Classic Binary Search
function binarySearch(arr, target) {
let start = 0
let end = arr.length - 1
while (start <= end) {
let mid = Math.floor((start + end) / 2)
if (arr[mid] === target) return mid
if (arr[mid] < target) start = mid + 1
if (arr[mid] > target) end = mid - 1
}
return - 1
}
2. Modified Binary Search
function modifiedBinarySearch(arr, target) {
let start = 0;
let end = arr.length - 1;
let result = -1; // Initialize result
while (start <= end) {
let mid = Math.floor((start + end) / 2);
// Exact match
if (arr[mid] === target) {
result = mid;
// For the first occurrence, keep going left
end = mid - 1;
}
// Standard binary search logic
if (arr[mid] < target) {
start = mid + 1;
} else {
end = mid - 1;
}
}
return result;
}
Remember, the "Modified Condition" is the part you'd customize based on what specific problem you're tackling.
3. Find the Closest Element to a Target
Here, you have to find the closest element to a given target in a sorted array.
function closestElement(arr, target) {
let start = 0, end = arr.length - 1;
while (start < end) {
let mid = Math.floor((start + end) / 2);
if (arr[mid] === target) return mid;
if (Math.abs(arr[mid] - target) <= Math.abs(arr[mid + 1] - target)) {
end = mid;
} else {
start = mid + 1;
}
}
return start;
}
4. Find the Peak Element
In an array where adjacent elements are distinct, find a peak element. An element is considered peak if it is greater than its neighbors.
function findPeakElement(arr) {
let start = 0, end = arr.length - 1;
while (start < end) {
let mid = Math.floor((start + end) / 2);
if (arr[mid] < arr[mid + 1]) {
start = mid + 1;
} else {
end = mid;
}
}
return start;
}
5. Find Rotation Point in a Rotated Sorted Array
For a rotated sorted array, find the index where the smallest element is.
function findRotationPoint(arr) {
let start = 0, end = arr.length - 1;
while (start < end) {
let mid = Math.floor((start + end) / 2);
if (arr[mid] > arr[end]) {
start = mid + 1;
} else {
end = mid;
}
}
return start;
}
6. Find First and Last Position of an Element
In a sorted array with duplicates, find the starting and ending position of a given target value.
function searchRange(arr, target) {
let start = 0, end = arr.length - 1, first = -1, last = -1;
while (start <= end) {
let mid = Math.floor((start + end) / 2);
if (arr[mid] === target) {
first = mid;
end = mid - 1;
} else if (arr[mid] < target) {
start = mid + 1;
} else {
end = mid - 1;
}
}
start = 0, end = arr.length - 1;
while (start <= end) {
let mid = Math.floor((start + end) / 2);
if (arr[mid] === target) {
last = mid;
start = mid + 1;
} else if (arr[mid] < target) {
start = mid + 1;
} else {
end = mid - 1;
}
}
return [first, last];
}
Knowing when to use binary search depends on several factors, such as the problem constraints and the properties of the data. Here are some general guidelines:
When to Use Binary Search
Sorted Data: The most fundamental prerequisite for binary search is that the data must be sorted.
Time Complexity: If the problem requires better than O(n)O(n)O(n) time complexity, binary search often becomes a candidate with its O(logn)O(\log n)O(logn) time.
Constant Space: If you need to solve the problem with constant extra space, binary search can be a good choice since it only requires pointers like
start,end, andmid.Multiple Queries: In cases where there are multiple queries on static data, preparing a sorted structure for binary search might be beneficial in the long run.
Search Conditions: If the problem involves searching for a particular condition rather than a specific element (e.g., find the point where a function changes behavior), binary search could apply.
When Not to Use Binary Search
Unsorted Data: If the data is not sorted and cannot be sorted in better than O(nlogn)O(n \log n)O(nlogn) time, then binary search is likely not a fit.
Updates: If the data set is being updated frequently, maintaining the sorted order might be costly unless specialized data structures like balanced trees are used.
Linear Scanning is Enough: For smaller datasets or when O(n)O(n)O(n) time complexity is acceptable, a simpler linear search might suffice.
Exact Matches: If you're looking for a range or pair of values rather than an exact match, binary search might require modifications and might not be the most straightforward approach.
Space Complexity: When extra space is not a constraint, other techniques like Hashing might be simpler and more suitable for certain types of search problems.
When approaching a problem, look at the constraints and see if binary search can give you an edge in time complexity, or if the problem's nature naturally lends itself to a binary search approach.
LeetCode Binary Search
-
Standard Binary Search (Standard Binary Search)
-
Find First and Last Position of Element in Sorted Array (Standard Binary Search)
-
Search in Rotated Sorted Array (Rotated Array Binary Search)
-
Find Minimum in Rotated Sorted Array (Rotated Array Binary Search)
-
Closest Element to a Target (Standard Binary Search)
-
Find Peak Element (Modified Binary Search)
-
Find the Smallest or Largest Element Greater Than a Given Number (Modified Binary Search)
-
Find Kth Element (Modified Binary Search)
-
Variable Length Arrays (String, Range Queries) (Modified Binary Search)
-
Others (Miscellaneous)
Points of note to study
- Classic Binary Search vs. Modified Binary Search
-
while(start <= end)vs.while(start < end)
