Binary Search

In this video lesson we will learn about the concept of searching, linear searching and more important - Binary Searching:

Problem:

Given a sorted array of integers nums, use Binary Search to find and return the index of a given value.

If the value doesn't exist in nums, return -1.

Example 1:

Input: nums = [1, 2, 4, 5], value = 4
Output: 2
Explanation: nums[2] is 4

Note:

Your algorithm should run in O(log n) time and use O(1) extra space.

Introduction

Binary Search is a fundamental algorithm in computer science used to find the position of a target value within a sorted array. It is highly efficient with a time complexity of O(log n), making it significantly faster than linear search for large datasets. Binary Search is widely used in various applications such as searching in databases, libraries, and even in competitive programming.

Understanding the Basics

Binary Search works by repeatedly dividing the search interval in half. If the value of the search key is less than the item in the middle of the interval, the search continues in the lower half, or if the value is greater, it continues in the upper half. This process continues until the value is found or the interval is empty.

For example, consider the sorted array [1, 2, 4, 5] and we want to find the value 4. The algorithm will start by comparing 4 with the middle element 2. Since 4 is greater, it will then search in the right half, and so on.

Main Concepts

The key concepts in Binary Search include:

Midpoint Calculation: Calculate the middle index of the current search interval.
Comparison: Compare the target value with the middle element.
Interval Adjustment: Adjust the search interval based on the comparison result.

Let's see how to apply these concepts in code:

/**
 * Function to perform binary search on a sorted array
 * @param {number[]} nums - Sorted array of integers
 * @param {number} value - Target value to search for
 * @return {number} - Index of the target value or -1 if not found
 */
function binarySearch(nums, value) {
  // Initialize the left and right pointers
  let left = 0;
  let right = nums.length - 1;

  // Loop until the search interval is valid
  while (left <= right) {
    // Calculate the middle index
    const mid = Math.floor((left + right) / 2);

    // Check if the middle element is the target value
    if (nums[mid] === value) {
      return mid; // Target value found
    } else if (nums[mid] < value) {
      left = mid + 1; // Adjust the left pointer
    } else {
      right = mid - 1; // Adjust the right pointer
    }
  }

  // Target value not found
  return -1;
}

// Example usage
const nums = [1, 2, 4, 5];
const value = 4;
console.log(binarySearch(nums, value)); // Output: 2

Examples and Use Cases

Let's consider a few more examples to understand the application of Binary Search:

Example 2:
Input: nums = [1, 3, 5, 7, 9], value = 7
Output: 3
Explanation: nums[3] is 7

Example 3:
Input: nums = [2, 4, 6, 8, 10], value = 5
Output: -1
Explanation: 5 is not in the array

Common Pitfalls and Best Practices

When implementing Binary Search, it's important to avoid common mistakes such as:

Incorrect midpoint calculation, which can lead to infinite loops.
Not updating the search interval correctly.

Best practices include:

Using integer division to calculate the midpoint.
Ensuring the search interval is adjusted correctly after each comparison.

Advanced Techniques

Advanced techniques related to Binary Search include:

Binary Search on a rotated sorted array: This involves additional logic to handle the rotation.
Finding the first or last occurrence of a target value: This requires slight modifications to the standard Binary Search algorithm.

Code Implementation

Here is the complete code implementation of Binary Search with comments explaining each step:

/**
 * Function to perform binary search on a sorted array
 * @param {number[]} nums - Sorted array of integers
 * @param {number} value - Target value to search for
 * @return {number} - Index of the target value or -1 if not found
 */
function binarySearch(nums, value) {
  // Initialize the left and right pointers
  let left = 0;
  let right = nums.length - 1;

  // Loop until the search interval is valid
  while (left <= right) {
    // Calculate the middle index
    const mid = Math.floor((left + right) / 2);

    // Check if the middle element is the target value
    if (nums[mid] === value) {
      return mid; // Target value found
    } else if (nums[mid] < value) {
      left = mid + 1; // Adjust the left pointer
    } else {
      right = mid - 1; // Adjust the right pointer
    }
  }

  // Target value not found
  return -1;
}

// Example usage
const nums = [1, 2, 4, 5];
const value = 4;
console.log(binarySearch(nums, value)); // Output: 2

Debugging and Testing

When debugging Binary Search, consider the following tips:

Print the values of the left, right, and mid pointers at each step to trace the algorithm's execution.
Check edge cases such as an empty array or a single-element array.

To test the Binary Search function, you can write test cases using a testing framework like Jest:

// Jest test cases for binarySearch function
test('binarySearch finds the target value', () => {
  expect(binarySearch([1, 2, 4, 5], 4)).toBe(2);
  expect(binarySearch([1, 3, 5, 7, 9], 7)).toBe(3);
  expect(binarySearch([2, 4, 6, 8, 10], 5)).toBe(-1);
  expect(binarySearch([], 1)).toBe(-1);
  expect(binarySearch([1], 1)).toBe(0);
});

Thinking and Problem-Solving Tips

When approaching problems related to Binary Search, consider the following strategies:

Clearly define the search interval and update it correctly after each comparison.
Break down the problem into smaller parts and solve each part step-by-step.
Practice with different types of problems to improve your understanding and skills.

Conclusion

Binary Search is a powerful algorithm for efficiently finding elements in a sorted array. By mastering Binary Search, you can solve a wide range of problems more effectively. Remember to practice regularly and explore advanced techniques to deepen your understanding.

Additional Resources

For further reading and practice problems, consider the following resources: