DEV Community

Cover image for Mastering Binary Search
Clean Code Studio
Clean Code Studio

Posted on

Mastering Binary Search

#datastructures #algorithms #interview #javascript


LeetCode Practice Problems for each Binary Search Implementation and Variation Linked Below

(My personal study notes)

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 }
Enter fullscreen mode Exit fullscreen mode

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; }
Enter fullscreen mode Exit fullscreen mode

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; }
Enter fullscreen mode Exit fullscreen mode

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; }
Enter fullscreen mode Exit fullscreen mode

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; }
Enter fullscreen mode Exit fullscreen mode

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]; }
Enter fullscreen mode Exit fullscreen mode

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

  1. Sorted Data: The most fundamental prerequisite for binary search is that the data must be sorted.

  2. 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(log⁡n)O(\log n)O(logn) time.

  3. 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, and mid.

  4. 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.

  5. 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

  1. Unsorted Data: If the data is not sorted and cannot be sorted in better than O(nlog⁡n)O(n \log n)O(nlogn) time, then binary search is likely not a fit.

  2. 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.

  3. 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.

  4. 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.

  5. 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

  1. Standard Binary Search (Standard Binary Search)

  2. Find First and Last Position of Element in Sorted Array (Standard Binary Search)

  3. Search in Rotated Sorted Array (Rotated Array Binary Search)

  4. Find Minimum in Rotated Sorted Array (Rotated Array Binary Search)

  5. Closest Element to a Target (Standard Binary Search)

  6. Find Peak Element (Modified Binary Search)

  7. Find the Smallest or Largest Element Greater Than a Given Number (Modified Binary Search)

  8. Find Kth Element (Modified Binary Search)

  9. Variable Length Arrays (String, Range Queries) (Modified Binary Search)

  10. Others (Miscellaneous)

Points of note to study

Top comments (0)