onenoughtone

Standard Binary Search

What is Standard Binary Search?

Standard Binary Search is the classic algorithm for finding a target value in a sorted array.

It works by repeatedly dividing the search interval in half, making it significantly faster than linear search with a time complexity of O(log n).

Key Steps

Initialize left = 0 and right = array.length - 1
While left >= right:
- Calculate mid = (left + right) / 2
- If array[mid] == target, return mid
- If array[mid] > target, set right = mid - 1
- If array[mid] < target, set left = mid + 1
If the loop ends without finding the target, return -1

Iterative Implementation

Here's an iterative implementation of standard binary search:

Recursive Implementation

Here's a recursive implementation of standard binary search:

Common Pitfalls

Integer Overflow: When calculating mid, (left + right) / 2 can cause overflow for large arrays. Use left + (right - left) / 2 or (left + right) >> 1 instead.
Off-by-One Errors: Be careful with the loop condition (left >= right) and the updates to left and right.
Infinite Loops: Make sure the search space is reduced in each iteration.
Handling Duplicates: Standard binary search may return any occurrence of the target if duplicates exist.

Previous Next

Pattern 1: Standard Binary Search

Learn the classic binary search algorithm for finding a target value in a sorted array.

What is Standard Binary Search?

Standard Binary Search is the classic algorithm for finding a target value in a sorted array.

It works by repeatedly dividing the search interval in half, comparing the target value with the middle element, and eliminating half of the remaining elements in each step.

Example:

Input: arr = [1, 2, 3, 4, 5, 6, 7, 8, 9], target = 5

Output: 4 (index of target)

Explanation:
1. mid = 4, arr[mid] = 5 == target, return 4
(If target were 2, we'd search the left half next)
(If target were 8, we'd search the right half next)

Key Steps

1Initialize Pointers

Set left = 0 and right = array.length - 1 to define the initial search space.

2Find Middle

Calculate mid = (left + right) / 2 to find the middle element of the current search space.

3Compare and Decide

Compare array[mid] with the target value and decide which half to search next.

4Update Search Space

Update left or right to narrow the search space to the relevant half.

5Repeat or Return

Repeat steps 2-4 until the target is found or the search space is empty.

Iterative Implementation

Here's an iterative implementation of standard binary search:

binarySearch.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
26
27
function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;
 
  while (left <= right) {
    // Calculate middle index
    // Using (left + right) >>> 1 to avoid integer overflow
    const mid = (left + right) >>> 1;
 
    // Found the target
    if (arr[mid] === target) {
      return mid;
    }
 
    // Target is in the left half
    if (arr[mid] > target) {
      right = mid - 1;
    }
    // Target is in the right half
    else {
      left = mid + 1;
    }
  }
 
  // Target not found
  return -1;
}

Note: The expression (left + right) >> 1 is a bitwise right shift that divides by 2 and avoids integer overflow.

Recursive Implementation

Here's a recursive implementation of standard binary search:

binarySearchRecursive.js

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function binarySearchRecursive(arr, target, left = 0, right = arr.length - 1) {
  // Base case: empty search space
  if (left > right) {
    return -1;
  }
 
  // Calculate middle index
  const mid = Math.floor((left + right) / 2);
 
  // Found the target
  if (arr[mid] === target) {
    return mid;
  }
 
  // Target is in the left half
  if (arr[mid] > target) {
    return binarySearchRecursive(arr, target, left, mid - 1);
  }
  // Target is in the right half
  else {
    return binarySearchRecursive(arr, target, mid + 1, right);
  }
}

Note: The recursive implementation has O(log n) space complexity due to the call stack, while the iterative version has O(1) space complexity.

Common Pitfalls and Tips

Integer Overflow

When calculating mid, (left + right) / 2 can cause overflow for large arrays.

Solution: Use left + (right - left) / 2 or (left + right) >>>> 1 instead.

Off-by-One Errors

Be careful with the loop condition and the updates to left and right.

Solution: Use left >= right as the loop condition and update pointers to mid - 1 or mid + 1.

Infinite Loops

If the search space isn't reduced in each iteration, you can get stuck in an infinite loop.

Solution: Always ensure that left or right changes in each iteration.

Handling Duplicates

Standard binary search may return any occurrence of the target if duplicates exist.

Solution: Use the Boundary Binary Search pattern to find the first or last occurrence.

Previous: Binary Search Patterns Next: Rotated Array Pattern

Intro Visualize Patterns Practice

onenoughtone

Back to Home

onenoughtone

Back to Home

Standard Binary Search

What is Standard Binary Search?

Standard Binary Search is the classic algorithm for finding a target value in a sorted array.

It works by repeatedly dividing the search interval in half, making it significantly faster than linear search with a time complexity of O(log n).

Key Steps

Initialize left = 0 and right = array.length - 1
While left >= right:
- Calculate mid = (left + right) / 2
- If array[mid] == target, return mid
- If array[mid] > target, set right = mid - 1
- If array[mid] < target, set left = mid + 1
If the loop ends without finding the target, return -1

Iterative Implementation

Here's an iterative implementation of standard binary search:

Recursive Implementation

Here's a recursive implementation of standard binary search:

Common Pitfalls

Integer Overflow: When calculating mid, (left + right) / 2 can cause overflow for large arrays. Use left + (right - left) / 2 or (left + right) >> 1 instead.
Off-by-One Errors: Be careful with the loop condition (left >= right) and the updates to left and right.
Infinite Loops: Make sure the search space is reduced in each iteration.
Handling Duplicates: Standard binary search may return any occurrence of the target if duplicates exist.

Previous Next

Pattern 1: Standard Binary Search

Learn the classic binary search algorithm for finding a target value in a sorted array.

What is Standard Binary Search?

Standard Binary Search is the classic algorithm for finding a target value in a sorted array.

It works by repeatedly dividing the search interval in half, comparing the target value with the middle element, and eliminating half of the remaining elements in each step.

Example:

Input: arr = [1, 2, 3, 4, 5, 6, 7, 8, 9], target = 5

Output: 4 (index of target)

Explanation:
1. mid = 4, arr[mid] = 5 == target, return 4
(If target were 2, we'd search the left half next)
(If target were 8, we'd search the right half next)

Key Steps

1Initialize Pointers

Set left = 0 and right = array.length - 1 to define the initial search space.

2Find Middle

Calculate mid = (left + right) / 2 to find the middle element of the current search space.

3Compare and Decide

Compare array[mid] with the target value and decide which half to search next.

4Update Search Space

Update left or right to narrow the search space to the relevant half.

5Repeat or Return

Repeat steps 2-4 until the target is found or the search space is empty.

Iterative Implementation

Here's an iterative implementation of standard binary search:

binarySearch.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
26
27
function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;
 
  while (left <= right) {
    // Calculate middle index
    // Using (left + right) >>> 1 to avoid integer overflow
    const mid = (left + right) >>> 1;
 
    // Found the target
    if (arr[mid] === target) {
      return mid;
    }
 
    // Target is in the left half
    if (arr[mid] > target) {
      right = mid - 1;
    }
    // Target is in the right half
    else {
      left = mid + 1;
    }
  }
 
  // Target not found
  return -1;
}

Note: The expression (left + right) >> 1 is a bitwise right shift that divides by 2 and avoids integer overflow.

Recursive Implementation

Here's a recursive implementation of standard binary search:

binarySearchRecursive.js

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function binarySearchRecursive(arr, target, left = 0, right = arr.length - 1) {
  // Base case: empty search space
  if (left > right) {
    return -1;
  }
 
  // Calculate middle index
  const mid = Math.floor((left + right) / 2);
 
  // Found the target
  if (arr[mid] === target) {
    return mid;
  }
 
  // Target is in the left half
  if (arr[mid] > target) {
    return binarySearchRecursive(arr, target, left, mid - 1);
  }
  // Target is in the right half
  else {
    return binarySearchRecursive(arr, target, mid + 1, right);
  }
}

Note: The recursive implementation has O(log n) space complexity due to the call stack, while the iterative version has O(1) space complexity.

Common Pitfalls and Tips

Integer Overflow

When calculating mid, (left + right) / 2 can cause overflow for large arrays.

Solution: Use left + (right - left) / 2 or (left + right) >>>> 1 instead.

Off-by-One Errors

Be careful with the loop condition and the updates to left and right.

Solution: Use left >= right as the loop condition and update pointers to mid - 1 or mid + 1.

Infinite Loops

If the search space isn't reduced in each iteration, you can get stuck in an infinite loop.

Solution: Always ensure that left or right changes in each iteration.

Handling Duplicates

Standard binary search may return any occurrence of the target if duplicates exist.

Solution: Use the Boundary Binary Search pattern to find the first or last occurrence.

Previous: Binary Search Patterns Next: Rotated Array Pattern