onenoughtone

Boundary Binary Search

What is Boundary Binary Search?

Boundary Binary Search is a pattern used to find the boundary between two regions in a sorted array, such as the first or last occurrence of a value, or the insertion point for a new value.

Unlike standard binary search which returns as soon as it finds a match, boundary binary search continues searching even after finding a match to locate the exact boundary.

Key Variations

First Occurrence: Finding the first occurrence of a target value in a sorted array with duplicates
Last Occurrence: Finding the last occurrence of a target value in a sorted array with duplicates
Insertion Point: Finding the position where a target value should be inserted to maintain the sorted order
Peak Element: Finding a peak element in an array (an element greater than its neighbors)

Finding the First Occurrence

Here's how to find the first occurrence of a target value in a sorted array:

Finding the Last Occurrence

Here's how to find the last occurrence of a target value in a sorted array:

Finding the Insertion Point

Here's how to find the position where a target value should be inserted to maintain the sorted order:

Previous Next

Pattern 4: Boundary Binary Search

Learn how to find boundaries between regions in sorted arrays using binary search.

What is Boundary Binary Search?

Boundary Binary Search is a pattern used to find the boundary between two regions in a sorted array, such as the first or last occurrence of a value, or the insertion point for a new value.

Unlike standard binary search which returns as soon as it finds a match, boundary binary search continues searching even after finding a match to locate the exact boundary.

Example:

Input: arr = [1, 2, 2, 2, 3, 4, 5], target = 2

First Occurrence: 1 (index of the first 2)

Last Occurrence: 3 (index of the last 2)

Explanation: Standard binary search might return any index between 1 and 3, but boundary binary search can find the exact first or last occurrence.

Key Variations

First Occurrence

Finding the first occurrence of a target value in a sorted array with duplicates.

Last Occurrence

Finding the last occurrence of a target value in a sorted array with duplicates.

Insertion Point

Finding the position where a target value should be inserted to maintain the sorted order.

Peak Element

Finding a peak element in an array (an element greater than its neighbors).

Finding the First Occurrence

Here's how to find the first occurrence of a target value in a sorted array:

findFirstOccurrence.js

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
function findFirstOccurrence(arr, target) {
  let left = 0;
  let right = arr.length - 1;
  let result = -1;
 
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
 
    // Found a potential result
    if (arr[mid] === target) {
      result = mid; // Save this as a potential result
      right = mid - 1; // Continue searching in the left half
    }
    // Target is in the right half
    else if (arr[mid] < target) {
      left = mid + 1;
    }
    // Target is in the left half
    else {
      right = mid - 1;
    }
  }
 
  return result;
}

How it works: When we find a match, we save the current index as a potential result, but we continue searching in the left half to find an earlier occurrence. This way, we'll eventually find the leftmost occurrence of the target.

Finding the Last Occurrence

Here's how to find the last occurrence of a target value in a sorted array:

findLastOccurrence.js

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
function findLastOccurrence(arr, target) {
  let left = 0;
  let right = arr.length - 1;
  let result = -1;
 
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
 
    // Found a potential result
    if (arr[mid] === target) {
      result = mid; // Save this as a potential result
      left = mid + 1; // Continue searching in the right half
    }
    // Target is in the right half
    else if (arr[mid] < target) {
      left = mid + 1;
    }
    // Target is in the left half
    else {
      right = mid - 1;
    }
  }
 
  return result;
}

How it works: When we find a match, we save the current index as a potential result, but we continue searching in the right half to find a later occurrence. This way, we'll eventually find the rightmost occurrence of the target.

Finding the Insertion Point

Here's how to find the position where a target value should be inserted to maintain the sorted order:

searchInsert.js

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
function 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;
    }
 
    if (nums[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
 
  // At this point, left > right
  // left is the position where target should be inserted
  return left;
}

How it works: We perform a standard binary search for the target. If we find it, we return its index. If we don't find it, the loop will exit with left > right, and left will be the position where the target should be inserted to maintain the sorted order.

Common Applications

Count Occurrences

Count the number of occurrences of a target value in a sorted array.

Solution: Find the first and last occurrences, then calculate lastIndex - firstIndex + 1.

Find Range

Find the range of indices where a target value appears in a sorted array.

Solution: Return [firstIndex, lastIndex] using the first and last occurrence algorithms.

Find Closest Element

Find the element in a sorted array that is closest to a target value.

Solution: Use binary search to find the insertion point, then compare the elements at insertPoint - 1 and insertPoint (if they exist).

Find Peak Element

Find a peak element in an array (an element greater than its neighbors).

Solution: Use binary search to find a position where arr[mid] > arr[mid+1], then search in the appropriate half.

Previous: Search Space Reduction Next: Practice Problems

Intro Visualize Patterns Practice

onenoughtone

Back to Home

onenoughtone

Back to Home

Boundary Binary Search

What is Boundary Binary Search?

Boundary Binary Search is a pattern used to find the boundary between two regions in a sorted array, such as the first or last occurrence of a value, or the insertion point for a new value.

Unlike standard binary search which returns as soon as it finds a match, boundary binary search continues searching even after finding a match to locate the exact boundary.

Key Variations

First Occurrence: Finding the first occurrence of a target value in a sorted array with duplicates
Last Occurrence: Finding the last occurrence of a target value in a sorted array with duplicates
Insertion Point: Finding the position where a target value should be inserted to maintain the sorted order
Peak Element: Finding a peak element in an array (an element greater than its neighbors)

Finding the First Occurrence

Here's how to find the first occurrence of a target value in a sorted array:

Finding the Last Occurrence

Here's how to find the last occurrence of a target value in a sorted array:

Finding the Insertion Point

Here's how to find the position where a target value should be inserted to maintain the sorted order:

Previous Next

Pattern 4: Boundary Binary Search

Learn how to find boundaries between regions in sorted arrays using binary search.

What is Boundary Binary Search?

Boundary Binary Search is a pattern used to find the boundary between two regions in a sorted array, such as the first or last occurrence of a value, or the insertion point for a new value.

Unlike standard binary search which returns as soon as it finds a match, boundary binary search continues searching even after finding a match to locate the exact boundary.

Example:

Input: arr = [1, 2, 2, 2, 3, 4, 5], target = 2

First Occurrence: 1 (index of the first 2)

Last Occurrence: 3 (index of the last 2)

Explanation: Standard binary search might return any index between 1 and 3, but boundary binary search can find the exact first or last occurrence.

Key Variations

First Occurrence

Finding the first occurrence of a target value in a sorted array with duplicates.

Last Occurrence

Finding the last occurrence of a target value in a sorted array with duplicates.

Insertion Point

Finding the position where a target value should be inserted to maintain the sorted order.

Peak Element

Finding a peak element in an array (an element greater than its neighbors).

Finding the First Occurrence

Here's how to find the first occurrence of a target value in a sorted array:

findFirstOccurrence.js

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
function findFirstOccurrence(arr, target) {
  let left = 0;
  let right = arr.length - 1;
  let result = -1;
 
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
 
    // Found a potential result
    if (arr[mid] === target) {
      result = mid; // Save this as a potential result
      right = mid - 1; // Continue searching in the left half
    }
    // Target is in the right half
    else if (arr[mid] < target) {
      left = mid + 1;
    }
    // Target is in the left half
    else {
      right = mid - 1;
    }
  }
 
  return result;
}

Finding the Last Occurrence

Here's how to find the last occurrence of a target value in a sorted array:

findLastOccurrence.js

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
function findLastOccurrence(arr, target) {
  let left = 0;
  let right = arr.length - 1;
  let result = -1;
 
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
 
    // Found a potential result
    if (arr[mid] === target) {
      result = mid; // Save this as a potential result
      left = mid + 1; // Continue searching in the right half
    }
    // Target is in the right half
    else if (arr[mid] < target) {
      left = mid + 1;
    }
    // Target is in the left half
    else {
      right = mid - 1;
    }
  }
 
  return result;
}

Finding the Insertion Point

Here's how to find the position where a target value should be inserted to maintain the sorted order:

searchInsert.js

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
function 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;
    }
 
    if (nums[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
 
  // At this point, left > right
  // left is the position where target should be inserted
  return left;
}

Common Applications

Count Occurrences

Count the number of occurrences of a target value in a sorted array.

Solution: Find the first and last occurrences, then calculate lastIndex - firstIndex + 1.

Find Range

Find the range of indices where a target value appears in a sorted array.

Solution: Return [firstIndex, lastIndex] using the first and last occurrence algorithms.

Find Closest Element

Find the element in a sorted array that is closest to a target value.

Solution: Use binary search to find the insertion point, then compare the elements at insertPoint - 1 and insertPoint (if they exist).

Find Peak Element

Find a peak element in an array (an element greater than its neighbors).

Solution: Use binary search to find a position where arr[mid] > arr[mid+1], then search in the appropriate half.

Previous: Search Space Reduction Next: Practice Problems