Binary search کیسے کام کرتا ہے، اور اس کے لیے کیا ضروری ہے؟

Question

Accepted Answer

**Binary search** ایک **sorted** array میں target کو تلاش کرتا ہے اور بار بار search range کو نصف کرتا ہے۔ ہر موازنہ باقی ماندہ عناصر کا نصف حذف کر دیتا ہے، جس سے **O(log n)** وقت ملتا ہے۔ ## نظریہ درمیانی عنصر کو دیکھیں۔ اگر یہ target کے برابر ہے تو ہو گیا۔ اگر target چھوٹا ہے تو بائیں نصف میں تلاش کریں؛ اگر بڑا ہے تو دائیں نصف میں تلاش کریں۔ جب تک نہ مل جائے یا range خالی نہ ہو جائے دہراتے رہیں۔ ## مثال ```python def binary_search(arr, target): lo, hi = 0, len(arr) - 1 while lo <= hi: mid = (lo + hi) // 2 # middle index if arr[mid] == target: return mid # found it elif arr[mid] < target: lo = mid + 1 # discard left half else: hi = mid - 1 # discard right half return -1 # not present binary_search([1, 3, 5, 7, 9], 7) # -> 3 ``` ## ٹریس ```text Search 7 in [1,3,5,7,9] lo=0 hi=4 mid=2 -> 5 < 7 => lo=3 lo=3 hi=4 mid=3 -> 7 == 7 => return 3 ``` ## Complexity - **Time:** O(log n)۔ **Space:** O(1) iterative۔ ## نقصانات **input sorted ہونی چاہیے** — ورنہ نتائج بے معنی ہیں۔ `lo`/`hi` میں off-by-one bugs سے احتیاط کریں اور کچھ languages میں integer overflow سے (use `lo + (hi-lo)//2`)۔ ## یہ کیوں اہم ہے Search space کو نصف کرنے سے ایک ملین عناصر کی تلاش تقریباً 20 موازنوں میں بدل جاتی ہے۔ اس کے پیچھے divide-and-conquer pattern درختوں، ڈیٹا بیسز، اور بے شمار interview مسائل میں دوبارہ ظاہر ہوتا ہے۔ اس کی ایک سخت ضرورت — sorted input — کو جاننا آپ کو ایک عام لطیف bug سے بچاتا ہے۔