DSA Tutorial

🔄 Process: Divide the array and narrow down the search range, halving it each time.

Algorithm

• Start with the middle element of the sorted array.
• If the target element is equal to the middle element, return the index.
• If the target element is less than the middle element, narrow the search to the left half.
• If the target element is greater than the middle element, narrow the search to the right half.
• Repeat the process until the element is found or the array is exhausted.

Pseudo Code

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

💻 C Code Example

#include <stdio.h>

int binarySearch(int arr[], int n, int target) {
    int left = 0, right = n - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (arr[mid] == target) {
            return mid;  // Element found, return index
        }
        else if (arr[mid] < target) {
            left = mid + 1;  // Search in the right half
        }
        else {
            right = mid - 1;  // Search in the left half
        }
    }
    return -1;  // Element not found
}

int main() {
    int arr[] = {2, 5, 7, 9, 11, 15};
    int n = 6;
    int target = 9;
    int result = binarySearch(arr, n, target);

    if (result != -1)
        printf("Element found at index %d\n", result);
    else
        printf("Element not found\n");

    return 0;
}
    

⏱ Time Complexity

The time complexity of Binary Search is O(log n), where 'n' is the number of elements in the array. This is much faster than Linear Search (O(n)) for large datasets, as it reduces the search range by half with each step.

📊 Binary Search vs. Linear Search:
- Binary Search is ideal for large, sorted arrays (O(log n) time complexity).
- Linear Search works on unsorted or small arrays (O(n) time complexity).

🚀 Try Binary Search with Your Own Example:
- Create a sorted array of integers.
- Select a target value.
- Implement the binary search algorithm to find if the target exists in the array.