Binary Search Algorithm – Complete Guide for GATE CSE 2026
Binary Search is most important searching algorithm for GATE. 2 marks pakke every year.
What is Binary Search?
Binary Search works only on Sorted Array. It divides array into half again and again.
Condition: Array must be sorted.
Algorithm in Simple Hinglish
1. low = 0, high = n-1
2. While low <= high:
mid = (low+high)//2
If arr[mid] == target: Found!
If arr[mid] < target: Search in right half (low = mid+1)
If arr[mid] > target: Search in left half (high = mid-1)
Python Code for GATE
def binary_search(arr, target):
low = 0
high = len(arr) - 1
while low <= high:
mid = (low + high) // 2
if arr[mid] == target:
return mid # Found at index mid
elif arr[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1 # Not found
arr = [10, 20, 30, 40, 50]
print(binary_search(arr, 30)) # Output: 2
Time Complexity – GATE Favorite Question
| Case | Complexity |
|---|---|
| Best Case (middle me mil gaya) | O(1) |
| Worst Case | O(log n) |
| Average Case | O(log n) |
| Space Complexity | O(1) iterative, O(log n) recursive |
GATE PYQ on Binary Search
Q1. GATE CSE 2021 – How many comparisons?
Q: Sorted array of size 16, worst case comparisons for binary search?
Ans: ceil(log2(16)) + 1 = 5 comparisons. Formula: log2(n) + 1
Q2. GATE CSE 2019 – Binary vs Linear
Q: Array size n=1000, Binary search vs Linear search?
Ans: Linear O(n)=1000 comparisons, Binary O(log n)=10 comparisons. Binary is much faster!
Q3. GATE CSE 2020 – Recursive Binary Search
def binary(arr, low, high, x):
if low > high:
return -1
mid = (low+high)//2
if arr[mid] == x:
return mid
elif arr[mid] > x:
return binary(arr, low, mid-1, x)
else:
return binary(arr, mid+1, high, x)
Ans: Recursive version uses stack memory O(log n).
Linear Search vs Binary Search – GATE Table
| Feature | Linear Search | Binary Search |
|---|---|---|
| Sorted Needed? | No | Yes |
| Time | O(n) | O(log n) |
| GATE Use | Small array | Large sorted array |
Conclusion
Remember for GATE: Binary Search = Sorted Array + O(log n) + Divide and Conquer. Practice 10 PYQ.
Next Post: Last Post – OS Deadlock GATE Questions (10th Post)