Skip to main content
Mapagam

Implementing Binary Search Variations

1. Understanding Binary Search Template

Component Description Example
Initialization Set up left and right pointers int left = 0, right = arr.length - 1;
Loop Condition Continue while left <= right while (left <= right)
Mid Calculation Calculate mid to avoid overflow int mid = left + (right - left) / 2;
Comparison Logic Compare mid value with target if (arr[mid] == target) return mid;
Pointer Adjustment Adjust left or right based on comparison if (arr[mid] < target) left = mid + 1;

Example: Basic Binary Search Implementation

public static int binarySearch(int[] arr, int target) {
    int left = 0;
    int right = arr.length - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return -1; // Not found
}
Note: The template ensures O(log n) time complexity by halving the search space in each iteration.

2. Searching Insert Position

Variant Description Implementation Time Complexity
Leftmost Insert Position Finds the leftmost position to insert a value to keep array sorted 
function searchInsertLeft(nums, target) {
  let left = 0;
  let right = nums.length;

  while (left < right) {
    const mid = Math.floor((left + right) / 2);
    if (nums[mid] < target) {
      left = mid + 1;
    } else {
      right = mid;
    }
  }

  return left;
}
 O(log n)
Rightmost Insert Position Finds the rightmost position to insert a value to keep array sorted 
function searchInsertRight(nums, target) {
  let left = 0;
  let right = nums.length;

  while (left < right) {
    const mid = Math.floor((left + right) / 2);
    if (nums[mid] <= target) {
      left = mid + 1;
    } else {
      right = mid;
    }
  }

  return left;
}
 O(log n)

Example: Insert Position in Sorted Array

const nums = [1, 3, 5, 6];
const target = 5;

// Leftmost insert position
console.log(searchInsertLeft(nums, target)); // Output: 2

// Rightmost insert position
console.log(searchInsertRight(nums, target)); // Output: 3

3. Finding Square Root

Approach Description Time Complexity Space Complexity
Binary Search on Answer Space Use binary search to find the square root by searching in the range [0, n] for a value whose square is close to n O(log n) O(1) 
function findSquareRoot(n) {
  if (n < 0) return NaN;
  if (n === 0 || n === 1) return n;

  let left = 0;
  let right = n;
  let epsilon = 1e-7; // Precision for floating point comparison

  while (left <= right) {
    let mid = left + (right - left) / 2;
    let square = mid * mid;

    if (Math.abs(square - n) <= epsilon) {
      return mid;
    } else if (square < n) {
      left = mid;
    } else {
      right = mid;
    }
  }

  return left;
}

// Example usage:
console.log(findSquareRoot(25)); // Output: 5
console.log(findSquareRoot(2));  // Output: ~1.414
Note: The binary search is performed on the value space, not the index space. The precision epsilon is used to handle floating-point inaccuracies.

4. Finding Closest Element

Property Description Example
closestElement Finds the element in a sorted array closest to a target value using binary search. 
function closestElement(arr, target) {
  let left = 0;
  let right = arr.length - 1;
  while (left <= right) {
    let mid = Math.floor((left + right) / 2);
    if (arr[mid] === target) return arr[mid];
    else if (arr[mid] < target) left = mid + 1;
    else right = mid - 1;
  }
  let leftDiff = Math.abs(arr[left] - target);
  let rightDiff = Math.abs(arr[right] - target);
  return leftDiff <= rightDiff ? arr[left] : arr[right];
}

Example: Finding Closest Element

const arr = [1, 3, 5, 7, 9];
const target = 6;
console.log(closestElement(arr, target)); // Output: 5

5. Finding Peak Element

A peak element in an array is an element that is greater than or equal to its neighbors. For arrays with multiple peaks, any peak can be returned.

Property Description Notes
Array Input array of integers Can contain duplicates
Peak Condition Element >= neighbors For edge elements, only one neighbor is considered

Example: Finding Peak Element

function findPeakElement(arr) {
  if (arr.length === 1) return 0;
  
  // Check first element
  if (arr[0] >= arr[1]) return 0;
  
  // Check last element
  if (arr[arr.length - 1] >= arr[arr.length - 2]) return arr.length - 1;
  
  // Check middle elements
  for (let i = 1; i < arr.length - 1; i++) {
    if (arr[i] >= arr[i - 1] && arr[i] >= arr[i + 1]) {
      return i;
    }
  }
  
  return -1; // Should not happen in valid input
}

// Example usage:
const nums = [1, 2, 3, 1];
console.log(findPeakElement(nums)); // Output: 2 (element 3 is peak)
Note: The linear approach has O(n) time complexity. A more efficient O(log n) solution can be achieved using binary search.

Example: Binary Search for Peak Element

function findPeakElementBinary(arr) {
  let left = 0;
  let right = arr.length - 1;
  
  while (left < right) {
    let mid = Math.floor((left + right) / 2);
    
    // If mid element is smaller than its right neighbor,
    // a peak must exist on the right side
    if (arr[mid] < arr[mid + 1]) {
      left = mid + 1;
    } else {
      // Otherwise, a peak must exist on the left side (including mid)
      right = mid;
    }
  }
  
  return left;
}

// Example usage:
const nums2 = [1, 2, 3, 4, 5, 6, 7];
console.log(findPeakElementBinary(nums2)); // Output: 6 (element 7 is peak)

6. Finding First and Last Position

Property Description Usage
findFirstPosition Finds the first occurrence of a target value in a sorted array. Useful for determining the starting index of a repeated element.
findLastPosition Finds the last occurrence of a target value in a sorted array. Useful for determining the ending index of a repeated element.

Example: Finding First and Last Position

function findFirstPosition(arr, target) {
    let left = 0;
    let right = arr.length - 1;
    let result = -1;

    while (left <= right) {
        let mid = Math.floor((left + right) / 2);
        if (arr[mid] === target) {
            result = mid;
            right = mid - 1; // Continue searching on the left
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return result;
}

function findLastPosition(arr, target) {
    let left = 0;
    let right = arr.length - 1;
    let result = -1;

    while (left <= right) {
        let mid = Math.floor((left + right) / 2);
        if (arr[mid] === target) {
            result = mid;
            left = mid + 1; // Continue searching on the right
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return result;
}

// Example usage:
const arr = [1, 2, 2, 2, 3, 4, 4, 5];
const target = 2;
console.log(findFirstPosition(arr, target)); // Output: 1
console.log(findLastPosition(arr, target));  // Output: 3

Summary of Approach

  • findFirstPosition adjusts the search to find the leftmost occurrence by moving right to mid - 1 when the target is found.
  • findLastPosition adjusts the search to find the rightmost occurrence by moving left to mid + 1 when the target is found.
  • Both functions maintain O(log n) time complexity.

7. Finding K Closest Elements

Property Description Example
array Sorted array of integers [1, 2, 3, 4, 5]
k Number of closest elements to find 2
x Target value to find closest elements to 3

Example: Finding K Closest Elements

function findClosestElements(arr, k, x) {
  let left = 0;
  let right = arr.length - k;

  while (left < right) {
    let mid = Math.floor((left + right) / 2);
    if (x - arr[mid] > arr[mid + k] - x) {
      left = mid + 1;
    } else {
      right = mid;
    }
  }

  return arr.slice(left, left + k);
}

// Example usage:
const arr = [1, 2, 3, 4, 5];
const k = 2;
const x = 3;
console.log(findClosestElements(arr, k, x)); // [2, 3]
Note: This algorithm uses binary search to efficiently find the starting index of the k closest elements in a sorted array.

8. Finding Smallest Letter Greater Than Target

Property Description Example
Input Sorted array of lowercase letters and a target letter letters = ['c', 'f', 'j'], target = 'd'
Output Smallest letter in the array that is greater than target 'f'
Edge Case If target is greater than or equal to the largest letter, wrap around to the first letter letters = ['c', 'f', 'j'], target = 'k' → 'c'

Example: Implementation

function nextGreatestLetter(letters, target) {
    let left = 0;
    let right = letters.length - 1;

    while (left <= right) {
        let mid = Math.floor((left + right) / 2);
        if (letters[mid] <= target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return letters[left % letters.length];
}

// Example usage:
const letters = ['c', 'f', 'j'];
const target = 'd';
console.log(nextGreatestLetter(letters, target)); // Output: 'f'
Note: The solution uses binary search to efficiently find the smallest letter greater than target. If no such letter exists, it wraps around to the first letter in the array.

9. Searching in Rotated Sorted Array

Property Description Notes
rotatedArray Array that was originally sorted but rotated at some pivot point Assumes no duplicates in the array
target Element to search for in the rotated array Can be any integer value present in the array

Example: Searching in Rotated Sorted Array

function searchInRotatedArray(nums, target) {
  let left = 0;
  let right = nums.length - 1;

  while (left <= right) {
    let mid = Math.floor((left + right) / 2);

    if (nums[mid] === target) return mid;

    // Check if left half is sorted
    if (nums[left] <= nums[mid]) {
      if (nums[left] <= target && target < nums[mid]) {
        right = mid - 1;
      } else {
        left = mid + 1;
      }
    } else {
      // Right half is sorted
      if (nums[mid] < target && target <= nums[right]) {
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }
  }

  return -1;
}

// Example usage:
const nums = [4, 5, 6, 7, 0, 1, 2];
console.log(searchInRotatedArray(nums, 0)); // Output: 4
Note: The key insight is to determine which half of the array is sorted and whether the target lies within that range.

10. Finding Minimum in Rotated Array

Property Description Notes
Array Rotated sorted array with unique elements Example: [4, 5, 6, 7, 0, 1, 2]
Goal Find the minimum element in O(log n) time Use binary search logic

Example: Finding Minimum in Rotated Array

function findMinInRotatedArray(nums) {
    let left = 0;
    let right = nums.length - 1;

    while (left < right) {
        const mid = Math.floor((left + right) / 2);

        if (nums[mid] > nums[right]) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }

    return nums[left];
}

// Example usage:
const arr = [4, 5, 6, 7, 0, 1, 2];
console.log(findMinInRotatedArray(arr)); // Output: 0
Note: The key insight is comparing nums[mid] with nums[right] to determine which half contains the minimum.

11. Searching in 2D Matrix

Property Description Notes
matrix 2D array of integers sorted row-wise and column-wise Each row is sorted left to right, each column top to bottom
target Integer value to search for in the matrix Can be any integer within the matrix range

Example: Searching in a 2D Matrix

function searchMatrix(matrix, target) {
  if (!matrix || matrix.length === 0 || matrix[0].length === 0) return false;

  let row = 0;
  let col = matrix[0].length - 1;

  while (row < matrix.length && col >= 0) {
    if (matrix[row][col] === target) return true;
    else if (matrix[row][col] > target) col--;
    else row++;
  }

  return false;
}

// Example usage:
const matrix = [
  [1,   4,  7, 11],
  [2,   5,  8, 12],
  [3,   6,  9, 16],
  [10, 13, 14, 17]
];
console.log(searchMatrix(matrix, 5)); // true
console.log(searchMatrix(matrix, 15)); // false
Note: This approach starts from the top-right corner and moves either left or down based on comparison with target, achieving O(m+n) time complexity.

12. Finding Single Element in Sorted Array

Property Description Example
Array Sorted array where every element appears exactly twice except one [1, 1, 2, 3, 3, 4, 4]
Target Element that appears only once 2

Example: Binary Search Implementation

function findSingleElement(nums) {
    let left = 0;
    let right = nums.length - 1;

    while (left < right) {
        let mid = Math.floor((left + right) / 2);
        // Ensure mid is even for comparison
        if (mid % 2 === 1) {
            mid--;
        }

        if (nums[mid] === nums[mid + 1]) {
            left = mid + 2;
        } else {
            right = mid;
        }
    }

    return nums[left];
}

// Example usage:
const arr = [1, 1, 2, 3, 3, 4, 4];
console.log(findSingleElement(arr)); // Output: 2
Note: The algorithm uses binary search to achieve O(log n) time complexity by checking pairs of elements.

Was this article helpful?

Related Cheat Sheets