37.implement-Binary-Search-unique.md

37. implement Binary Search (unique)

The binary search technique is an efficient algorithm for finding an item from a sorted list of items. It works by repeatedly dividing in half the portion of the list that could contain the item, until you've narrowed down the possible locations to just one.

Steps in Binary Search:

1. Initial Setup:

   • Start with two pointers, left and right, which initially point to the beginning and the end of the array, respectively.

2. Find the Middle Element:

   • Calculate the middle index mid as the average of left and right. This is usually done as:

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

3. Compare the Middle Element:

   • If the middle element arr[mid] is equal to the target value, the search is complete, and the index mid is returned.
   • If the target value is less than the middle element, the target must be in the left half of the array. Adjust the right pointer to mid - 1.
   • If the target value is greater than the middle element, the target must be in the right half of the array. Adjust the left pointer to mid + 1.

4. Repeat:

   • Repeat the process, recalculating the middle index and adjusting the pointers, until left exceeds right. If left exceeds right, it means the target is not in the array, and the search returns -1.

Characteristics of Binary Search:

• Efficiency: The time complexity of binary search is O(log⁡n)O(\log n)O(logn), making it much faster than linear search for large datasets.
• Requirement: Binary search requires the array to be sorted beforehand. If the array is not sorted, binary search will not work correctly.
• Implementation: Binary search can be implemented iteratively or recursively.

Problem

https://bigfrontend.dev/problem/implement-Binary-Search-Unique

Problem Description

Even in Front-End review, basic algorithm technique like Binary Search are likely to be asked.

You are given an unique & ascending array of integers, please search for its index with Binary Search.

If not found, return -1

Iterative Solution

/**
 * @param {number[]} arr - ascending unique array
 * @param {number} target
 * @return {number}
 */
function binarySearch(arr, target) {
  let start = 0;
  let end = arr.length - 1;

  while (start <= end) {
    const mid = Math.floor((start + end) / 2);

    if (target === arr[mid]) {
      return mid;
    }

    if (target < arr[mid]) {
      end = mid - 1;
    } else {
      start = mid + 1;
    }
  }

  return -1;
}

// Usage 
console.log(binarySearch([1, 2, 3, 4, 5], 3)); // 2
console.log(binarySearch([1, 2, 3, 4, 5], 5)); // 4
console.log(binarySearch([1, 2, 3, 4, 5], 6)); // -1

Recursive Solution

/**
 * @param {number[]} arr - ascending unique array
 * @param {number} target
 * @return {number}
 */
function binarySearch(arr, target) {
  return recursiveBinarySearch(arr, target, 0, arr.length - 1);
}

function recursiveBinarySearch(arr, target, start, end) {
  if (start > end) {
    return -1;
  }

  const mid = Math.floor((start + end) / 2);

  if (arr[mid] === target) {
    return mid;
  }

  if (arr[mid] > target) {
    return recursiveBinarySearch(arr, target, start, mid - 1);
  }

  return recursiveBinarySearch(arr, target, mid + 1, end);
}

Use Cases

1. Searching in a Sorted Array:

• The primary use case for binary search is to find an element in a sorted array. It is significantly faster than linear search, especially for large datasets.

2. Finding Boundaries (Lower and Upper Bounds):

• Lower Bound: Finding the first occurrence of an element in a sorted array.
• Upper Bound: Finding the last occurrence of an element in a sorted array.
• These can be used to count the number of occurrences of a particular element by finding the difference between the upper and lower bounds.

3. Inserting in a Sorted Array:

• Binary search can determine the correct position to insert a new element in a sorted array, maintaining the array's order.

4. Finding the Smallest/Largest Satisfying a Condition:

• Binary search can be used to find the smallest or largest element that satisfies a particular condition. This is often used in optimization problems and threshold determination.

5. Search in Rotated Sorted Arrays:

• Binary search can be adapted to search in rotated sorted arrays (arrays that have been sorted and then rotated).

6. Efficient Search in a Range:

• Binary search can be used to efficiently search for elements within a specified range in a sorted array.

7. Finding the Square Root:

• Binary search can be used to compute the square root of a number by iteratively narrowing down the range of possible values.

8. Finding Peak Elements:

• In a given array, a peak element is an element that is greater than its neighbors. Binary search can efficiently find a peak element in an array.

9. Sparse Search:

• In a sorted array of strings with many empty strings, binary search can be adapted to handle sparse data.

10. Applications in Databases:

• Binary search is often used in database indexing to quickly locate data.

11. Applications in Computational Geometry:

• Problems like finding the intersection of line segments, point location problems, and others in computational geometry can use binary search.