Binary Search: Binary Search, Efficient Algorithms, Advanced Applications

#discuss #dsa #algorithms #atharvgyan

How Binary Search Works

Initial Setup: Start with two pointers, low and high, which represent the bounds of the search interval. Initially, low is set to 0, and high is set to the length of the array minus one.

Middle Element: Calculate the middle index mid of the current interval. The middle index is computed as mid = (low + high) // 2.

Comparison:

Repeat: Repeat steps 2 and 3 until the low pointer exceeds the high pointer. If the target value is not found, return -1 to indicate that the value is not in the array.

Binary Search Algorithm in Python

Here is the Python implementation of binary search:

python
<button style="--tw-border-spacing-x: 0; --tw-border-spacing-y: 0; --tw-ring-color: rgba(69,89,164,.5); --tw-ring-offset-color: #fff; --tw-ring-offset-shadow: 0 0 transparent; --tw-ring-offset-width: 0px; --tw-ring-shadow: 0 0 transparent; --tw-rotate: 0; --tw-scale-x: 1; --tw-scale-y: 1; --tw-scroll-snap-strictness: proximity; --tw-shadow-colored: 0 0 transparent; --tw-shadow: 0 0 transparent; --tw-skew-x: 0; --tw-skew-y: 0; --tw-translate-x: 0; --tw-translate-y: 0; align-items: center; appearance: button; background-image: none; border-color: rgb(227, 227, 227); border-style: solid; border-width: 0px; cursor: pointer; display: flex; font-family: inherit; font-feature-settings: inherit; font-size: 15px; font-variation-settings: inherit; font-weight: inherit; gap: 0.25rem; letter-spacing: inherit; line-height: inherit; margin: 0px; padding: 0px;"><br></button>

`def binary_search(arr, target):
    low = 0
    high = len(arr) - 1

    while low <= high:
        mid = (low + high) // 2
        mid_value = arr[mid]

        if mid_value == target:
            return mid # Target found, return its index
        elif mid_value < 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
sorted_array = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
target = 7

result = binary_search(sorted_array, target)
if result != -1:
    print(f"Element {target} found at index {result}")
else:
    print(f"Element {target} not found in the array")
`

Explanation of the Example

Initial State:
First Iteration:
Second Iteration:
Third Iteration:
Fourth Iteration:

Visual Representation

Imagine the array as follows:

makefile
<button style="--tw-border-spacing-x: 0; --tw-border-spacing-y: 0; --tw-ring-color: rgba(69,89,164,.5); --tw-ring-offset-color: #fff; --tw-ring-offset-shadow: 0 0 transparent; --tw-ring-offset-width: 0px; --tw-ring-shadow: 0 0 transparent; --tw-rotate: 0; --tw-scale-x: 1; --tw-scale-y: 1; --tw-scroll-snap-strictness: proximity; --tw-shadow-colored: 0 0 transparent; --tw-shadow: 0 0 transparent; --tw-skew-x: 0; --tw-skew-y: 0; --tw-translate-x: 0; --tw-translate-y: 0; align-items: center; appearance: button; background-image: none; border-color: rgb(227, 227, 227); border-style: solid; border-width: 0px; cursor: pointer; display: flex; font-family: inherit; font-feature-settings: inherit; font-size: 15px; font-variation-settings: inherit; font-weight: inherit; gap: 0.25rem; letter-spacing: inherit; line-height: inherit; margin: 0px; padding: 0px;"><br></button>

Index: 0 1 2 3 4 5 6 7 8 9 Array: 1 3 5 7 9 11 13 15 17 19 Target: 7


Initial bounds: low = 0, high = 9
After first iteration: mid = 4, high = 3
After second iteration: mid = 1, low = 2
After third iteration: mid = 2, low = 3
After fourth iteration: mid = 3, found target at index 3
Recursive Implementation of Binary Search
Binary search can also be implemented recursively. The recursive approach follows the same logic as the iterative approach but uses function calls to reduce the search range. Here's how you can implement it:

Recursive Binary Search Algorithm in Python

python

`def binary_search_recursive(arr, target, low, high):
if low > high:
return -1 # Base case: target is not found

mid = (low + high) // 2
mid_value = arr[mid]

if mid_value == target:
    return mid # Target found, return its index
elif mid_value < target:
    return binary_search_recursive(arr, target, mid + 1, high) # Search in the right half
else:
    return binary_search_recursive(arr, target, low, mid - 1) # Search in the left half

Example usage

sorted_array = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
target = 7

result = binary_search_recursive(sorted_array, target, 0, len(sorted_array) - 1)
if result != -1:
print(f"Element {target} found at index {result}")
else:
print(f"Element {target} not found in the array")
`

Explanation of the Recursive Example

Initial Call: binary_search_recursive(arr, 7, 0, 9)

Second Call: binary_search_recursive(arr, 7, 0, 3)

Third Call: binary_search_recursive(arr, 7, 2, 3)

Fourth Call: binary_search_recursive(arr, 7, 3, 3)

Visual Representation for Recursive Approach
The process of narrowing down the search interval in the recursive approach can be visualized similarly to
the iterative approach:

Initial bounds: low = 0, high = 9
After first recursive call: mid = 4, high = 3
After second recursive call: mid = 1, low = 2
After third recursive call: mid = 2, low = 3
After fourth recursive call: mid = 3, found target at index 3
Time Complexity
The time complexity of binary search, both iterative and recursive, is 𝑂(log⁡𝑛)O(logn), where 𝑛n is the number of elements in the array. This efficiency makes binary search suitable for large sorted datasets.

Advantages of Binary Search

Efficiency: With a time complexity of 𝑂(log⁡𝑛)O(logn), binary search is much faster than linear search for large datasets.

Simplicity: The algorithm is straightforward and easy to implement.

Deterministic: Binary search always follows the same steps and guarantees finding the target if it exists in the array.

Practical Considerations

Sorted Array: Binary search requires the array to be sorted. If the array is not sorted, you must sort it first, which takes 𝑂(𝑛log⁡𝑛)O(nlogn) time.

Non-recursive Approach: In practice, the iterative approach is often preferred over the recursive one because it avoids the overhead of recursive function calls, especially in languages with limited stack size.

Applications of Binary Search

Binary search is a versatile algorithm with numerous applications beyond simply finding an element in an array.

Here are some key applications:

Finding the Lower/Upper Bound:

Lower Bound: The smallest index at which a given value could be inserted to maintain sorted order.

Upper Bound: The largest index at which a given value could be inserted to maintain sorted order.

Searching in Infinite Lists:

Used in situations where the list size is not known, such as in certain streaming data applications.

Optimization Problems:

Binary search can be used to solve optimization problems where you need to find the minimum or maximum value that satisfies certain conditions.

Example: Finding the Lower Bound
The lower bound of a value in a sorted array is the index of the first element that is not less than the target value. Here’s how you can find the lower bound using binary search:

Read more...⇲