Day 25

Day 25: Binary Search and Its Variations

25/60 Days

Binary Search and Its Variations #

Welcome to Day 25 of our 60 Days of Coding Algorithm Challenge! Today, we’ll explore Binary Search, a fundamental search algorithm, and its various variations. Binary Search is known for its efficiency in searching sorted arrays and forms the basis for many other algorithms.

Introduction to Binary Search #

Binary Search is a divide and conquer algorithm that finds the position of a target value within a sorted array. It compares the target value to the middle element of the array; if they are unequal, the half in which the target cannot lie is eliminated and the search continues on the remaining half until the target value is found.

Basic Binary Search #

Here’s an implementation of the basic binary search algorithm:

 1def binary_search(arr, target):
 2    left, right = 0, len(arr) - 1
 3    
 4    while left <= right:
 5        mid = (left + right) // 2
 6        if arr[mid] == target:
 7            return mid
 8        elif arr[mid] < target:
 9            left = mid + 1
10        else:
11            right = mid - 1
12    
13    return -1  # Target not found
14
15# Example usage
16arr = [1, 3, 5, 7, 9, 11, …

Binary Search and Its Variations #

Introduction to Binary Search #

Basic Binary Search #

Here’s an implementation of the basic binary search algorithm:

 1def binary_search(arr, target):
 2    left, right = 0, len(arr) - 1
 3    
 4    while left <= right:
 5        mid = (left + right) // 2
 6        if arr[mid] == target:
 7            return mid
 8        elif arr[mid] < target:
 9            left = mid + 1
10        else:
11            right = mid - 1
12    
13    return -1  # Target not found
14
15# Example usage
16arr = [1, 3, 5, 7, 9, 11, 13, 15]
17target = 7
18result = binary_search(arr, target)
19print(f"Target {target} found at index: {result}")

Time Complexity: O(log n) Space Complexity: O(1)

Variations of Binary Search #

1. Recursive Binary Search #

A recursive implementation of binary search:

 1def recursive_binary_search(arr, target, left, right):
 2    if left > right:
 3        return -1
 4    
 5    mid = (left + right) // 2
 6    if arr[mid] == target:
 7        return mid
 8    elif arr[mid] < target:
 9        return recursive_binary_search(arr, target, mid + 1, right)
10    else:
11        return recursive_binary_search(arr, target, left, mid - 1)
12
13# Example usage
14arr = [1, 3, 5, 7, 9, 11, 13, 15]
15target = 11
16result = recursive_binary_search(arr, target, 0, len(arr) - 1)
17print(f"Target {target} found at index: {result}")

2. Finding the First Occurrence #

Modified binary search to find the first occurrence of a target value:

 1def first_occurrence(arr, target):
 2    left, right = 0, len(arr) - 1
 3    result = -1
 4    
 5    while left <= right:
 6        mid = (left + right) // 2
 7        if arr[mid] == target:
 8            result = mid
 9            right = mid - 1  # Continue searching in the left half
10        elif arr[mid] < target:
11            left = mid + 1
12        else:
13            right = mid - 1
14    
15    return result
16
17# Example usage
18arr = [1, 2, 2, 2, 3, 4, 4, 5]
19target = 2
20result = first_occurrence(arr, target)
21print(f"First occurrence of {target} found at index: {result}")

3. Finding the Last Occurrence #

Modified binary search to find the last occurrence of a target value:

 1def last_occurrence(arr, target):
 2    left, right = 0, len(arr) - 1
 3    result = -1
 4    
 5    while left <= right:
 6        mid = (left + right) // 2
 7        if arr[mid] == target:
 8            result = mid
 9            left = mid + 1  # Continue searching in the right half
10        elif arr[mid] < target:
11            left = mid + 1
12        else:
13            right = mid - 1
14    
15    return result
16
17# Example usage
18arr = [1, 2, 2, 2, 3, 4, 4, 5]
19target = 4
20result = last_occurrence(arr, target)
21print(f"Last occurrence of {target} found at index: {result}")

4. Finding the Floor and Ceiling #

Binary search variations to find the floor (largest element smaller than or equal to target) and ceiling (smallest element larger than or equal to target):

 1def floor(arr, target):
 2    left, right = 0, len(arr) - 1
 3    result = -1
 4    
 5    while left <= right:
 6        mid = (left + right) // 2
 7        if arr[mid] == target:
 8            return arr[mid]
 9        elif arr[mid] < target:
10            result = arr[mid]
11            left = mid + 1
12        else:
13            right = mid - 1
14    
15    return result
16
17def ceiling(arr, target):
18    left, right = 0, len(arr) - 1
19    result = -1
20    
21    while left <= right:
22        mid = (left + right) // 2
23        if arr[mid] == target:
24            return arr[mid]
25        elif arr[mid] < target:
26            left = mid + 1
27        else:
28            result = arr[mid]
29            right = mid - 1
30    
31    return result
32
33# Example usage
34arr = [1, 3, 5, 7, 9, 11, 13, 15]
35target = 6
36floor_result = floor(arr, target)
37ceiling_result = ceiling(arr, target)
38print(f"Floor of {target}: {floor_result}")
39print(f"Ceiling of {target}: {ceiling_result}")

5. Search in Rotated Sorted Array #

A variation of binary search to find an element in a rotated sorted array:

 1def search_rotated(arr, target):
 2    left, right = 0, len(arr) - 1
 3    
 4    while left <= right:
 5        mid = (left + right) // 2
 6        if arr[mid] == target:
 7            return mid
 8        
 9        # Check if left half is sorted
10        if arr[left] <= arr[mid]:
11            if arr[left] <= target < arr[mid]:
12                right = mid - 1
13            else:
14                left = mid + 1
15        # Right half is sorted
16        else:
17            if arr[mid] < target <= arr[right]:
18                left = mid + 1
19            else:
20                right = mid - 1
21    
22    return -1  # Target not found
23
24# Example usage
25arr = [4, 5, 6, 7, 0, 1, 2]
26target = 0
27result = search_rotated(arr, target)
28print(f"Target {target} found at index: {result}")

Applications of Binary Search #

Database Systems: For efficient searching in indexed databases.
Version Control Systems: For finding when a bug was introduced (git bisect).
Machine Learning: In algorithms like decision trees and gradient descent.
Computer Graphics: In ray tracing and texture mapping.
Optimization Problems: For finding minimum or maximum values in unimodal functions.

Exercise #

Implement a binary search algorithm to find the square root of a number (up to a given precision).
Create a function that uses binary search to find the peak element in a bitonic array (an array that first increases, then decreases).
Implement a binary search algorithm to find the minimum element in a sorted and rotated array.

Summary #

Today, we explored Binary Search and its various applications. We implemented the basic binary search algorithm and several variations, including recursive binary search, finding first and last occurrences, floor and ceiling values, and searching in rotated sorted arrays.

Binary Search is a powerful technique that forms the basis for many efficient algorithms. Its logarithmic time complexity makes it invaluable for searching large datasets. As we progress through this challenge, you’ll find binary search being used as a building block for more complex algorithms and problem-solving techniques.

Tomorrow, we’ll dive into the Quicksort algorithm, one of the most efficient sorting algorithms. Stay tuned!

Binary Search and Its Variations #

Introduction to Binary Search #

Basic Binary Search #

Binary Search and Its Variations #

Introduction to Binary Search #

Basic Binary Search #

Variations of Binary Search #

1. Recursive Binary Search #

2. Finding the First Occurrence #

3. Finding the Last Occurrence #

4. Finding the Floor and Ceiling #

5. Search in Rotated Sorted Array #

Applications of Binary Search #

Exercise #

Summary #

Continue Reading

Re-enter Password

Confirm Action