Mastering Binary Search
Tags: datastructures, algorithms, interview, javascript
Published: 2023-10-16 00:22:28

<small><small>
[LeetCode Practice Problems](#LeetCode Binary Search) for each Binary Search Implementation and Variation Linked Below
</small></small>
<hr />
<center>(My personal study notes)</center>
<hr />
- [Mastering Binary Search](#mastering-binary-search)
   * [Variations of Binary Search (patterns to practice)](#variations-of-binary-search-patterns-to-practice)
      + [1. Classic Binary Search](#1-classic-binary-search)
      + [2. Modified Binary Search](#2-modified-binary-search)
      + [3. Find the Closest Element to a Target](#3-find-the-closest-element-to-a-target)
      + [4. Find the Peak Element](#4-find-the-peak-element)
      + [5. Find Rotation Point in a Rotated Sorted Array](#5-find-rotation-point-in-a-rotated-sorted-array)
      + [6. Find First and Last Position of an Element](#6-find-first-and-last-position-of-an-element)
      + [When to Use Binary Search](#when-to-use-binary-search)
      + [When Not to Use Binary Search](#when-not-to-use-binary-search)
   * [LeetCode Binary Search ](#leetcode-binary-search)
   * [Points of note to study](#points-of-note-to-study)

## Variations of Binary Search (patterns to practice)
Worth knocking these into muscle memory

### 1. Classic Binary Search
```js
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

```js
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.


```js
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.

```js
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.


```js
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.


```js
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

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 
<small><small>

1. **Standard Binary Search (Standard Binary Search)**
    - [Binary Search](https://leetcode.com/problems/binary-search/)


2. **Find First and Last Position of Element in Sorted Array (Standard Binary Search)**
    - [Find First and Last Position of Element in Sorted Array](https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/)

3. **Search in Rotated Sorted Array (Rotated Array Binary Search)**
    - [Search in Rotated Sorted Array](https://leetcode.com/problems/search-in-rotated-sorted-array/)
    - [Search in Rotated Sorted Array II](https://leetcode.com/problems/search-in-rotated-sorted-array-ii/)

4. **Find Minimum in Rotated Sorted Array (Rotated Array Binary Search)**
    - [Find Minimum in Rotated Sorted Array](https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/)
    - [Find Minimum in Rotated Sorted Array II](https://leetcode.com/problems/find-minimum-in-rotated-sorted-array-ii/)

5. **Closest Element to a Target (Standard Binary Search)**
    - [Closest Binary Search Tree Value](https://leetcode.com/problems/closest-binary-search-tree-value/)
  
6. **Find Peak Element (Modified Binary Search)**
    - [Find Peak Element](https://leetcode.com/problems/find-peak-element/)

7. **Find the Smallest or Largest Element Greater Than a Given Number (Modified Binary Search)**
    - [First Bad Version](https://leetcode.com/problems/first-bad-version/)
  
8. **Find Kth Element (Modified Binary Search)**
    - [Kth Smallest Element in a Sorted Matrix](https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/)
    - [Find Kth Smallest Pair Distance](https://leetcode.com/problems/find-k-th-smallest-pair-distance/)

9. **Variable Length Arrays (String, Range Queries) (Modified Binary Search)**
    - [Longest Increasing Subsequence](https://leetcode.com/problems/longest-increasing-subsequence/)
    - [Range Sum Query - Immutable](https://leetcode.com/problems/range-sum-query-immutable/)

10. **Others (Miscellaneous)**
    - [Search a 2D Matrix](https://leetcode.com/problems/search-a-2d-matrix/)
    - [Search a 2D Matrix II](https://leetcode.com/problems/search-a-2d-matrix-ii/)

</small>
</small>

## Points of note to study
- [Classic Binary Search](#1-classic-binary-search) vs. [Modified Binary Search](#2-modified-binary-search)
-  `while(start <= end)` vs. `while(start < end)`


---

<small>
- [Clean Code Studio](https://cleancode.studio)
- [Binary Search Algorithm](https://cleancode.studio/algorithms/mastering-binary-search)
</small>