The Project | About Us | Contribute | Donations | License
HOME My courses Completed
◄ Previous
◄

Binary Search and Variants

Next ►
►

Introduction

Binary Search is a fundamental algorithm in computer science used for finding an element in a sorted array. It operates 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 algorithm narrows the interval to the lower half. Otherwise, it narrows it to the upper half. This process continues until the value is found or the interval is empty.

Key Concepts

  • Sorted Array: Binary Search requires the array to be sorted.
  • Divide and Conquer: The algorithm divides the problem into smaller subproblems and solves them recursively.
  • Logarithmic Time Complexity: Binary Search operates in O(log n) time, making it very efficient for large datasets.

Basic Binary Search Algorithm

Pseudocode

function binarySearch(arr, target):
    low = 0
    high = length(arr) - 1
    
    while low <= high:
        mid = low + (high - low) / 2
        
        if arr[mid] == target:
            return mid
        else if arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    
    return -1

Explanation

  1. Initialization: Set low to 0 and high to the last index of the array.
  2. Loop: Continue the loop while low is less than or equal to high.
  3. Midpoint Calculation: Calculate the midpoint mid of the current interval.
  4. Comparison:
    • If arr[mid] equals the target, return mid.
    • If arr[mid] is less than the target, adjust low to mid + 1.
    • If arr[mid] is greater than the target, adjust high to mid - 1.
  5. Termination: If the target is not found, return -1.

Example

def binary_search(arr, target):
    low = 0
    high = len(arr) - 1
    
    while low <= high:
        mid = low + (high - low) // 2
        
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    
    return -1

# Example usage
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
target = 7
print(binary_search(arr, target))  # Output: 6

Variants of Binary Search

  1. Binary Search for First Occurrence

To find the first occurrence of a target value in a sorted array:

def binary_search_first_occurrence(arr, target):
    low = 0
    high = len(arr) - 1
    result = -1
    
    while low <= high:
        mid = low + (high - low) // 2
        
        if arr[mid] == target:
            result = mid
            high = mid - 1  # Continue searching in the left half
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    
    return result

# Example usage
arr = [1, 2, 2, 2, 3, 4, 5]
target = 2
print(binary_search_first_occurrence(arr, target))  # Output: 1

  1. Binary Search for Last Occurrence

To find the last occurrence of a target value in a sorted array:

def binary_search_last_occurrence(arr, target):
    low = 0
    high = len(arr) - 1
    result = -1
    
    while low <= high:
        mid = low + (high - low) // 2
        
        if arr[mid] == target:
            result = mid
            low = mid + 1  # Continue searching in the right half
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    
    return result

# Example usage
arr = [1, 2, 2, 2, 3, 4, 5]
target = 2
print(binary_search_last_occurrence(arr, target))  # Output: 3

  1. Binary Search for Insertion Point

To find the insertion point for a target value in a sorted array:

def binary_search_insertion_point(arr, target):
    low = 0
    high = len(arr) - 1
    
    while low <= high:
        mid = low + (high - low) // 2
        
        if arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    
    return low

# Example usage
arr = [1, 2, 4, 5, 6]
target = 3
print(binary_search_insertion_point(arr, target))  # Output: 2

Practical Exercises

Exercise 1: Basic Binary Search

Implement a binary search function that returns the index of a target value in a sorted array, or -1 if the target is not found.

def binary_search(arr, target):
    # Your code here
    pass

# Test cases
print(binary_search([1, 2, 3, 4, 5], 3))  # Expected output: 2
print(binary_search([1, 2, 3, 4, 5], 6))  # Expected output: -1

Solution

def binary_search(arr, target):
    low = 0
    high = len(arr) - 1
    
    while low <= high:
        mid = low + (high - low) // 2
        
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    
    return -1

# Test cases
print(binary_search([1, 2, 3, 4, 5], 3))  # Output: 2
print(binary_search([1, 2, 3, 4, 5], 6))  # Output: -1

Exercise 2: First Occurrence Binary Search

Implement a binary search function that returns the index of the first occurrence of a target value in a sorted array, or -1 if the target is not found.

def binary_search_first_occurrence(arr, target):
    # Your code here
    pass

# Test cases
print(binary_search_first_occurrence([1, 2, 2, 2, 3, 4, 5], 2))  # Expected output: 1
print(binary_search_first_occurrence([1, 2, 3, 4, 5], 6))  # Expected output: -1

Solution

def binary_search_first_occurrence(arr, target):
    low = 0
    high = len(arr) - 1
    result = -1
    
    while low <= high:
        mid = low + (high - low) // 2
        
        if arr[mid] == target:
            result = mid
            high = mid - 1  # Continue searching in the left half
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    
    return result

# Test cases
print(binary_search_first_occurrence([1, 2, 2, 2, 3, 4, 5], 2))  # Output: 1
print(binary_search_first_occurrence([1, 2, 3, 4, 5], 6))  # Output: -1

Conclusion

Binary Search is a powerful algorithm for searching in sorted arrays with a logarithmic time complexity. Understanding its basic implementation and variants is crucial for solving a wide range of computational problems efficiently. The exercises provided will help reinforce the concepts and ensure a solid grasp of binary search techniques.

◄ Previous
◄
Next ►
►
The Project | About Us | Contribute | Donations | License
© Copyright 2024. All rights reserved