Binary Search Algorithm (Iterative and Recursive)

Binary Search ek highly efficient searching algorithm hai jo Divide and Conquer paradigm par kaam karta hai. Binary search ki primary prerequisite yeh hai ki array pehle se sorted hona chahiye (ascending ya descending order me).

Binary search har step me search space ko aada (half) kar deta hai, jisse iski running time logarithmic ho jaati hai.

Working Mechanism

Search range ko maintain karne ke liye do pointers use hote hain: low = 0 aur high = n - 1. Har iteration me middle index calculate kiya jata hai:

mid = low + (high - low) / 2;   // Integer overflow avoid karne ke liye

• Agar A[mid] == Key: Search successful, index mid return karte hain.
• Agar Key < A[mid]: Target element left half me hoga, isliye high = mid - 1 set karte hain.
• Agar Key > A[mid]: Target element right half me hoga, isliye low = mid + 1 set karte hain.

Sorted Array: [ 10,  20,  30,  40,  50,  60,  70,  80,  90 ]
Index:          0    1    2    3    4    5    6    7    8
Target Key = 70

Pass 1: low=0, high=8 -> mid = (0+8)/2 = 4 (A[4] = 50)
        Key(70) > 50 -> Search Right Half: low = mid + 1 = 5

Pass 2: low=5, high=8 -> mid = (5+8)/2 = 6 (A[6] = 70)
        Key(70) == 70 -> Match Found at index 6!

Algorithms: Iterative and Recursive

1. Iterative Algorithm

BINARY_SEARCH_ITERATIVE(A, N, KEY)
1. Set low = 0, high = N - 1
2. While low <= high do:
3.     mid = low + (high - low) / 2
4.     If A[mid] == KEY then:
           Return mid
5.     Else If KEY < A[mid] then:
           high = mid - 1
6.     Else:
           low = mid + 1
7. End of While
8. Return -1 [Not Found]

2. Recursive Algorithm

BINARY_SEARCH_RECURSIVE(A, low, high, KEY)
1. If low > high then:
       Return -1
2. mid = low + (high - low) / 2
3. If A[mid] == KEY then:
       Return mid
4. Else If KEY < A[mid] then:
       Return BINARY_SEARCH_RECURSIVE(A, low, mid - 1, KEY)
5. Else:
       Return BINARY_SEARCH_RECURSIVE(A, mid + 1, high, KEY)

Complexity Comparison

• Best-case Time: O(1) jab element exactly pehle mid par mil jaye.
• Worst-case Time: O(log n) – Har step par input size half ho jata hai: n, n/2, n/4, ..., 1 => log2(n) steps.
• Space Complexity: Iterative version me O(1) auxiliary space, jabki Recursive version me O(log n) recursion call stack memory lagti hai.

Agli post me hum sorting start karenge: Bubble Sort Algorithm and Optimization.