Binary Search

What You’ll Learn 📚

• Core concepts of binary search
• Key terminology and definitions
• Simple and progressively complex examples
• Common questions and answers
• Troubleshooting common issues

Introduction to Binary Search

Binary search is an efficient algorithm for finding an item from a sorted list of items. It works by repeatedly dividing the portion of the list that could contain the item in half until you’ve narrowed down the possible locations to just one.

Think of binary search like looking for a word in a dictionary. You don’t start at the first page and flip through each page one by one. Instead, you open the dictionary somewhere in the middle, decide if you need to go forward or backward, and repeat until you find your word.

Key Terminology

• Algorithm: A step-by-step procedure for solving a problem or performing a task.
• Sorted List: A list where the elements are in a specific order, usually ascending or descending.
• Divide and Conquer: A strategy of solving a problem by breaking it down into smaller sub-problems, solving each one independently, and combining their solutions.

The Simplest Example

def binary_search(arr, target):
    low = 0
    high = len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid  # Target found
        elif arr[mid] < target:
            low = mid + 1  # Search in the right half
        else:
            high = mid - 1  # Search in the left half
    return -1  # Target not found

# Example usage
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]
target = 5
result = binary_search(arr, target)
print(f'Target found at index: {result}')

Progressively Complex Examples

function binarySearch(arr, target) {
    let low = 0;
    let high = arr.length - 1;
    while (low <= high) {
        const mid = Math.floor((low + high) / 2);
        if (arr[mid] === target) {
            return mid; // Target found
        } else if (arr[mid] < target) {
            low = mid + 1; // Search in the right half
        } else {
            high = mid - 1; // Search in the left half
        }
    }
    return -1; // Target not found
}

// Example usage
const arr = [1, 2, 3, 4, 5, 6, 7, 8, 9];
const target = 5;
const result = binarySearch(arr, target);
console.log(`Target found at index: ${result}`);

public class BinarySearch {
    public static int binarySearch(int[] arr, int target) {
        int low = 0;
        int high = arr.length - 1;
        while (low <= high) {
            int mid = (low + high) / 2;
            if (arr[mid] == target) {
                return mid; // Target found
            } else if (arr[mid] < target) {
                low = mid + 1; // Search in the right half
            } else {
                high = mid - 1; // Search in the left half
            }
        }
        return -1; // Target not found
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9};
        int target = 5;
        int result = binarySearch(arr, target);
        System.out.println("Target found at index: " + result);
    }
}

Common Questions and Answers

1. Why does binary search require a sorted list?

   Binary search relies on the order of elements to eliminate half of the remaining elements at each step. If the list is not sorted, this elimination process would not work correctly.

2. What is the time complexity of binary search?

   The time complexity of binary search is O(log n), where n is the number of elements in the list. This is because the search range is halved with each iteration.

3. Can binary search be used on unsorted lists?

   No, binary search is not suitable for unsorted lists. For unsorted data, a linear search would be necessary, which has a time complexity of O(n).

4. What happens if the target is not in the list?

   If the target is not in the list, the function will return -1, indicating that the target was not found.

Troubleshooting Common Issues

• Off-by-one errors: Ensure that your low and high pointers are correctly initialized and updated.
• Infinite loops: Check that your loop condition low <= high is correctly implemented to prevent infinite loops.
• Incorrect mid calculation: Use integer division or a method like Math.floor to calculate the midpoint correctly.

Common Pitfall: Forgetting to update low or high correctly can lead to infinite loops or incorrect results.

Practice Exercises

• Implement binary search in a different programming language of your choice.
• Modify the binary search algorithm to work with descending sorted lists.
• Try using binary search to find the first occurrence of a duplicate value in a sorted list.

Remember, practice makes perfect! The more you code, the more intuitive these concepts will become. Keep experimenting and don't hesitate to revisit this guide whenever you need a refresher. Happy coding! 🚀