[Documentation Update]: Add content for binary search

[ParnaRoyChowdhury777]

Is there an existing issue for this?

• [X] I have searched the existing issues

Issue Description

I want to add the content over here

Suggested Change

I want to add the content

Rationale

No response

Urgency

High

Acknowledgements

• [X] I have read the Contributing Guidelines
• [X] I'm a GSSOC'24 contributor
• [X] I have starred the repository
• [X] I have read and followed the Contribution Guidelines
• [X] I have followed the code style guidelines of this project
• [X] I have checked for any existing open issues that my pull request may address
• [X] I have ensured that my changes do not break any existing functionality
• [X] Each contributor is allowed to create a maximum of 4 issues per day. This helps us manage and address issues efficiently
• [X] I have read the resources for guidance listed below
• [X] I have not used AI-generated content (e.g., ChatGPT, other AI tools)
• [X] I have not used content from existing sites (e.g., text, images)
• [X] I have followed all security rules and only shared trusted resources

[github-actions[bot]]

Hi @ParnaRoyChowdhury777! Thanks for opening this issue. We appreciate your contribution to this open-source project. Your input is valuable and we aim to respond or assign your issue as soon as possible. Thanks again!

[Ajay-Dhangar]

@ParnaRoyChowdhury777 We need for this directory advance contents So, if you do define and explain in full details then I assign you.

[ParnaRoyChowdhury777]

@ParnaRoyChowdhury777 We need for this directory advance contents So, if you do define and explain in full details then I assign you.

Ok..I am sending the content

[ParnaRoyChowdhury777]

@Ajay-Dhangar here is the content ::

Binary Search

Binary search is a classic algorithm for finding an element in a sorted array. It repeatedly divides the search interval in half and compares the middle element of the interval to the target value. If the target value matches the middle element, the search is successful. Otherwise, the search continues in the half of the array that may contain the target value.

Why is Binary Search preferred over Linear Search?

1. Time Complexity:

   • Binary Search: O(log n)
   • Linear Search: O(n)
     Binary search divides the search space in half each time, making it much faster for large datasets.

2. Efficiency with Large Datasets:

   • Binary search is efficient for large datasets, requiring around 20 comparisons for a million elements.
   • Linear search would require, on average, 500,000 comparisons for the same dataset.

3. Data Requirements:

   • Binary Search: Requires sorted data.
   • Linear Search: Works with unsorted data but is slower for large datasets.

4. Predictability:

   • Binary search offers consistent performance.
   • Linear search performance varies based on the target element's position.

5. Use Cases:

   • Binary Search: Ideal for static, sorted data with frequent searches (e.g., database indexing, dictionary lookups).
   • Linear Search: Suitable for small datasets or frequently changing data where sorting is impractical.

Algorithm

1. Sort: Ensure the array is sorted in ascending order.
2. Initialize: Set two pointers, low and high, to the beginning and end of the array, respectively.
3. Iterate: While low is less than or equal to high:
   • Calculate the middle index: mid = (low + high) / 2.
   • Compare the middle element with the target value.
   • If the middle element is the target, return the index.
   • If the middle element is greater than the target, search the left half by setting high = mid - 1.
   • If the middle element is less than the target, search the right half by setting low = mid + 1.
4. End: If the target is not found, return an indication (e.g., -1).

Explanation

Recursive Approach

def binary_search_recursive(arr, low, high, target):
    if low > high:
        return -1  # Target not found

    mid = (low + high) // 2

    if arr[mid] == target:
        return mid
    elif arr[mid] > target:
        return binary_search_recursive(arr, low, mid - 1, target)
    else:
        return binary_search_recursive(arr, mid + 1, high, target)

Iterative Approach

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

    while low <= high:
        mid = (low + high) // 2

        if arr[mid] == target:
            return mid
        elif arr[mid] > target:
            high = mid - 1
        else:
            low = mid + 1

    return -1  # Target not found

Time Complexity Analysis

1. Recurrence Relation:

   • Each step of the algorithm reduces the search space by half.
   • If T(n) is the time complexity for an array of size n, then: T(n) = T(n/2) + O(1).

2. Master's Theorem:

   • The recurrence relation T(n) = T(n/2) + O(1) fits the form T(n) = aT(n/b) + f(n), where a = 1, b = 2, and f(n) = O(1).
   • According to Master's Theorem: T(n) = O(\log n)

3. Substitution Method:

   • Assume T(n) = O(\log n).
   • Substitute into the recurrence relation: T(n) = T(n/2) + O(1) = O(log n) + O(1) = O(log n)

Space Complexity

• The space complexity for the iterative approach is O(1) since it uses a constant amount of extra space.
• The space complexity for the recursive approach is O(log n) due to the recursive call stack.

Applications

• Searching in a Sorted Array: Efficiently find an element in a sorted array.
• Database Indexing: Quickly locate records in a sorted database.
• Debugging: Find the source of an error in a range of code or data.

Illustration

Initial State

Array: [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
Target: 7
low = 0, high = 9

Step 1

mid = (0 + 9) // 2 = 4
Array[mid] = 9
9 > 7, so high = mid - 1 = 3

Step 2

low = 0, high = 3
mid = (0 + 3) // 2 = 1
Array[mid] = 3
3 < 7, so low = mid + 1 = 2

Step 3

low = 2, high = 3
mid = (2 + 3) // 2 = 2
Array[mid] = 5
5 < 7, so low = mid + 1 = 3

Step 4

low = 3, high = 3
mid = (3 + 3) // 2 = 3
Array[mid] = 7
7 == 7, target found at index 3

Let us have a pictorial representation of the binary search algorithm to understand it better.

1. The array in which searching is to be performed is:

   

   Initial array

   
   Let x = 4 be the element to be searched.

2. Set two pointers low and high at the lowest and the highest positions respectively.

   

   Setting pointers

3. Find the middle element mid of the array i.e. arr[(low + high)/2] = 6.

   

   Mid element

4. If x == mid, then return mid. Else, compare the element to be searched with mid.

5. If x > mid, compare x with the middle element of the elements on the right side of mid. This is done by setting low to low = mid + 1.

6. Else, compare x with the middle element of the elements on the left side of mid. This is done by setting high to high = mid - 1.

   

   Finding mid element

7. Repeat steps 3 to 6 until low meets high.

   

   Mid element

8. x = 4 is found.

   

   Found

Binary search is a fundamental algorithm with wide-ranging applications, especially in scenarios requiring fast data retrieval from sorted datasets.

The last portion images are like this::