Binary Search Introduction

Binary Search Introduction One Shot

What is Binary Search?

Binary Search is an efficient searching technique used to find an element in a sorted collection.

Instead of checking every element one by one, Binary Search checks the middle element and decides which half of the array can still contain the answer.

This makes Binary Search much faster than linear search for large arrays.

Common Binary Search problems include:

• Search X in a sorted array

• Lower Bound

• Upper Bound

• Search Insert Position

• Floor of X

• Ceil of X

Binary Search is an efficient algorithm designed to find the position of a target value within a collection of data. Instead of scanning through the data one item at a time from start to finish, Binary Search works by repeatedly dividing the searchable portion of data in half.

How Binary Search Works

Binary Search works only when the search space follows a sorted or monotonic pattern.

Most Binary Search problems follow the same simple process:

• Initialize two pointers, low and high.

• Find the middle index of the current search space.

• Compare the middle value with the target.

• Discard the half where the answer cannot exist.

• Repeat until the answer is found or the search space becomes empty.

• The main idea is that every step reduces the search space by half.

Search X in a Sorted Array

Given a sorted array of integers and a target value X, determine if X exists in the array. If it does, return its index. If it does not exist, return -1.

For a detailed explanation, see the original TUF blog: Search X in a Sorted Array

Algorithm

• Edge Case: If the array is empty, immediately return -1 because no search can be conducted.

• Set two pointers: low = 0 (start of the array) and high = n - 1 (end of the array).

• Run a loop while low <= high:

  • Calculate the middle index: mid = low + (high - low) / 2.

  • If nums[mid] == X, the target is found. Immediately return mid.

  • If nums[mid] < X, the target must be in the right half. Update low = mid + 1 to discard the left half.

  • If nums[mid] > X, the target must be in the left half. Update high = mid - 1 to discard the right half.

• If the loop finishes and low crosses high, the target is not in the array. Return -1.

Dry Run

Complexity Analysis

Time Complexity: O(log N), N is the size of array, because the search space is cut in half at every step.

Space Complexity: O(1), as the search uses a few pointer variables without extra memory.

Lower Bound

Given a sorted array of integers and a target value X, find the index of the first element in the array that is greater than or equal to X. If no such element exists, return the size of the array (N).

For a detailed explanation, see the original TUF blog: Lower Bound

Algorithm

• Edge Case: If the array is empty, return 0 since that is the index where the boundary begins.

• Set two pointers: low = 0 (start of the array) and high = n - 1 (end of the array). Initialize ans = n to act as a fallback if no element satisfies the condition.

• Run a loop while low <= high:

  • Calculate mid = low + (high - low) / 2.

  • If nums[mid] >= X, this is a valid candidate. Save this position by setting ans = mid. Since you want the first occurrence, search the left half by setting high = mid - 1.

  • If nums[mid] < X, this element is too small. Move to the right half by setting low = mid + 1.

• Return ans after the loop terminates.

Dry Run

Complexity Analysis

Time Complexity: O(log N),N is the size of array, because we evaluate one middle element per step and halve the remaining search space.

Space Complexity: O(1), utilizing only fixed boundary pointers and an answer tracker variable.

Upper Bound

Given a sorted array of integers and a target value X, find the index of the first element in the array that is strictly greater than X. If no such element exists, return the size of the array (N).

For a detailed explanation, see the original TUF blog: Upper Bound

Algorithm

• Edge Case: If the array is empty, return 0.

• Set two pointers: low = 0 (start of the array) and high = n - 1 (end of the array). Initialize ans = n.

• Run a loop while low <= high:

  • Calculate mid = low + (high - low) / 2.

  • If nums[mid] > X, this element satisfies the strict condition. Record ans = mid and search the left side by setting high = mid - 1 to check for an earlier valid element.

  • If nums[mid] <= X, this element is not strictly greater than $X$. Move to the right side by setting low = mid + 1.

• Return ans.

Dry Run

Complexity Analysis

Time Complexity: O(log N),N is the size of array, because the search space is cut in half at every step.

Space Complexity: O(1), as the search uses a few pointer variables without extra memory.

Search Insert Position

Given a sorted array of distinct integers and a target value X, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

For a detailed explanation, see the original TUF blog: Search Insert Position

Algorithm

• Edge Case: If the array is empty, return 0 because the element will become the very first item in the list.

• Set two pointers: low = 0 (start of the array) and high = n - 1 (end of the array). Initialize ans = n.

• Run a loop while low <= high:

  • Calculate mid = low + (high - low) / 2.

  • If nums[mid] == X, you found the exact value. Return mid immediately.

  • If nums[mid] > X, this position could be where X belongs, or X might belong further to the left. Record ans = mid and update high = mid - 1.

  • If nums[mid] < X, the insertion spot must be further down the line. Update low = mid + 1.

• Return ans if an exact match was not found. (Note: The final value of low at the end of a standard binary search loop also naturally points to this insertion index).

Dry Run

Complexity Analysis

Time Complexity: O(log N),N is the size of array, matching the performance of a lower bound binary search.

Space Complexity: O(1), operating completely in place.

Find Floor

Given a sorted array of integers and a target value X, find the largest value in the array that is smaller than or equal to X. Return its index, or -1 if no such element exists.

For a detailed explanation, see the original TUF blog: Find Floor

Algorithm

• Edge Case: If the array is empty, or if the first element nums[0] is strictly greater than $X$, return -1 because no valid floor element can exist.

• Set two pointers: low = 0 (start of the array) and high = n - 1 (end of the array). Initialize ans = -1.

• Run a loop while low <= high:

  • Calculate mid = low + (high - low) / 2.

  • If nums[mid] <= X, this element is a valid candidate for the floor. Store ans = mid. Since you want the largest possible valid value, try to find a larger one by looking in the right half: low = mid + 1.

  • If nums[mid] > X, the element is too large to be a floor. Discard it and everything to its right by setting high = mid - 1.

• Return ans.

Dry Run

Complexity Analysis

Time Complexity: O(log N),N is the size of array, since we cut the valid catalog items in half with each iteration.

Space Complexity: O(1), requiring no extra auxiliary storage.

Find Ceil

Given a sorted array of integers and a target value X, find the smallest value in the array that is greater than or equal to X. Return its index, or -1 if no such element exists.

For a detailed explanation, see the original TUF blog: Find Ceil

Algorithm

• Edge Case: If the array is empty, or if the last element nums[n-1] is strictly less than X, return -1 because no element can satisfy the ceiling condition.

• Set two pointers: low = 0 (start of the array) and high = n - 1 (end of the array). Initialize ans = -1.

• Run a loop while low <= high:

  • Calculate mid = low + (high - low) / 2.

  • If nums[mid] >= X, this element is valid. Record ans = mid. Since you are looking for the smallest value that qualifies, search the left half by setting high = mid - 1.

  • If nums[mid] < X, the value is too small to be a ceiling. Search the right half by setting low = mid + 1.

• Return ans.

Dry Run

Complexity Analysis

Time Complexity: O(log N), N is the size of array, because the binary loop boundaries converge logarithmically.

Space Complexity: O(1), utilizing a constant amount of memory tracking variables.