Binary Search and Its Variants

Binary Search

Binary Search is a classic algorithm for finding an element in a sorted array. It works by repeatedly dividing the search interval in half. If the value of the search key is less than the item in the middle of the interval, narrow the interval to the lower half. Otherwise, narrow it to the upper half. Repeatedly check until the value is found or the interval is empty. Both low + Math.floor((high - low) / 2) and Math.floor(left + (right - left) / 2) are valid ways to compute the mid index in binary search and can be used to avoid integer overflow.

Basic Binary Search

Here is a basic implementation of Binary Search in JavaScript:

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

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

    if (arr[mid] === target) {
      return mid; // Target found at index mid
    } else if (arr[mid] < target) {
      left = mid + 1; // Search in the right half
    } else {
      right = mid - 1; // Search in the left half
    }
  }

  return -1; // Target not found
}

// Example usage
const nums = [1, 2, 3, 4, 5, 6, 7, 8, 9];
const target = 5;
console.log(binarySearch(nums, target)); // Output: 4

Finds the first position where the target could be inserted without violating the order.

const findLowerBound = (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;
};

Finds the first position where an element greater than the target appears.

const findUpperBound = (nums = [], target) => {
   let left = 0;
  let right = nums.length;

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

Finds the index of the smallest element greater than the target.

const findLeastGreater = (nums, key) => {
  const n = nums.length;
  let low = 0;
  let high = n - 1;
  let result = -1;

  while (low <= high) {
    const mid = low + Math.floor((high - low) / 2);
    if (nums[mid] > key) {
      result = mid;
      high = mid - 1;
    } else low = mid + 1;
  }
  return result;
};

Finds the index of the largest element less than the target.

const findGreatestLess = (nums, key) => {
  const n = nums.length;
  let low = 0;
  let high = n - 1;
  let result = -1;

  while (low <= high) {
    const mid = low + Math.floor((high - low) / 2);
    if (nums[mid] < key) {
      result = mid;
      low = mid + 1;
    } else high = mid - 1;
  }
  return result;
};

Finds the index at which a target value should be inserted to maintain the sorted order.

const searchInsert = (nums, target) => {
    let left = 0;
    let right = nums.length - 1;
    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        if (nums[mid] === target) {
            return mid;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return left;
};

Find Minimum in a Rotated Sorted Array

const findMin = (nums) => {
    let left = 0;
    let right = nums.length - 1;
    while (left < right) {
        let mid = Math.floor((left + right) / 2);
        if (nums[mid] > nums[right]) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return nums[left];
};

Search in Rotated Sorted Array

const search = (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;
        }
        if (nums[left] <= nums[mid]) {
            if (nums[left] <= target && target < nums[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        } else {
            if (nums[mid] < target && target <= nums[right]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
    }
    return -1;
};

Binary Search on Answer Pattern:

function binarySearchOnAnswer(rangeStart, rangeEnd, isValid) {
    let left = rangeStart;
    let right = rangeEnd;

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

        if (isValid(mid)) {
            right = mid; // mid might be the answer, search in the left half
        } else {
            left = mid + 1; // mid is too small, search in the right half
        }
    }

    return left; // or right, as left == right
}

// Example usage for a problem
const isValid = (value) => {
    // Define what makes a value valid in your specific problem
    // Return true if value meets the condition, false otherwise
};

Binary Search on Answer Pattern Problems

• Maximum Candies Allocated to K Children
• Minimized Maximum of Products Distributed to Any Store
• Koko Eating Bananas
• Minimum Limit of Balls in a Bag
• Minimum Speed to Arrive on Time
• Maximum Number of Removable Characters
• Minimum Time to Complete Trips
• Minimize Maximum of Array
• Maximize Happiness of Selected Children
• Minimize Max Distance to Gas Station
• Frog Jump II
• Minimum Time to Repair Cars
• Split Array Largest Sum
• Divide Chocolate
• Cutting Ribbons
• Find the Smallest Divisor Given a Threshold
• Magnetic Force Between Two Balls
• Minimum Total Distance Traveled
• Maximum Bags With Full Capacity of Rocks
• Maximum Number of Robots Within Budget
• Kth Smallest Element in a Sorted Matrix
• Median of a Matrix
• Minimize Maximum Distance to Place Houses
• Minimum Size Subarray Sum
• Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts
• Longest Increasing Subsequence (LIS)
• Finding Sqrt of a Number using Binary Search
• Nth Root of a Number using Binary Search
• Minimum Days to Make M Bouquets
• Kth Missing Positive Number
• Book Allocation Problem

Binary Search on 2D Matrix:

Consider a 2D matrix:

matrix = [ [1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60] ] This matrix has 3 rows and 4 columns.

Row Calculation: Math.floor(mid / cols) Here, mid is the current index in the flattened perspective, and cols is the number of columns in each row of the matrix This division gives the number of full rows completed before reaching the current element Column Calculation: The column number is calculated as mid % cols. The modulus operation gives the remainder, which corresponds to the column index within the row. Explanation with an Example Let's take an example where mid = 5 and cols = 4.

Row Calculation:

Math.floor(mid / cols) = Math.floor(5 / 4) = 1 This indicates that the element at index 5 in the flattened view is in row 1 of the matrix (0-based index). Column Calculation:

mid % cols = 5 % 4 = 1 This indicates that the element is at column 1 in the matrix (0-based index). Therefore, matrix[Math.floor(mid / cols)][mid % cols] corresponds to matrix[1][1], which is 11 in the given matrix.

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

    const rows = matrix.length;
    const cols = matrix[0].length;
    let left = 0;
    let right = rows * cols - 1;

    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        const midValue = matrix[Math.floor(mid / cols)][mid % cols];

        if (midValue === target) {
            return true;
        } else if (midValue < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return false;
}

// Example usage
const matrix = [
    [1, 3, 5, 7],
    [10, 11, 16, 20],
    [23, 30, 34, 60]
];
const target = 3;
const result = searchMatrix(matrix, target);
console.log(result); // Outputs: true