One of the most efficient search algorithms. Find any element in a sorted array in O(log n) time!
Understanding the Core Concept
تخيل إنك عايز تدور على كلمة في القاموس. هل هتبدأ من أول صفحة وتقلب صفحة صفحة؟ طبعاً لأ! ده هيكون بطيء جداً.
بدل كده، هتفتح القاموس من النص، تبص على الكلمة اللي قدامك:
لأنك في كل خطوة بتشيل نص العناصر من البحث!
مثال: لو عندك 1,000,000 عنصر:
البحث الثنائي بيشتغل بس على المصفوفات المُرتبة (Sorted)!
لو المصفوفة مش مترتبة، لازم ترتبها الأول أو تستخدم Linear Search.
حط مؤشر low على أول عنصر (index 0).
وحط مؤشر high على آخر عنصر (index = length - 1).
دول بيحددوا "النطاق" اللي بتدور فيه.
mid = (low + high) / 2
ده الـ index بتاع العنصر اللي في النص.
بنستخدم Math.floor() عشان ناخد رقم صحيح.
لو arr[mid] == target ← لقيناه! 🎉
لو arr[mid] > target ← الهدف في النص الشمال، حدث high = mid - 1
لو arr[mid] < target ← الهدف في النص اليمين، حدث low = mid + 1
استمر في تكرار الخطوات 2 و 3 طالما low <= high.
لو low > high ← العنصر مش موجود في المصفوفة.
Step-by-Step Walkthrough
low = 0 (أول عنصر)
high = 9 (آخر عنصر)
mid = (0 + 9) / 2 = 4
العنصر في النص: 16
16 < 23 ← الهدف في النص اليمين!
نحدث: low = mid + 1 = 5
low = 5
high = 9
mid = (5 + 9) / 2 = 7
العنصر في النص: 56
56 > 23 ← الهدف في النص الشمال!
نحدث: high = mid - 1 = 6
لاحظ: شيلنا 5 عناصر من البحث! (العناصر الباهتة)
low = 5
high = 6
mid = (5 + 6) / 2 = 5
العنصر في النص: 23
23 == 23 ← لقيناه!
الـ index بتاعه: 5
✅ لقينا العنصر في 3 خطوات بس من أصل 10 عناصر!
Complexity Analysis
لأننا في كل خطوة بنقسم المصفوفة على 2.
كام مرة نقدر نقسم n على 2 لحد ما نوصل لـ 1؟
الإجابة: log₂(n) مرة!
| n = 16 | log₂(16) = 4 خطوات |
| n = 1,000 | ~10 خطوات |
| n = 1,000,000 | ~20 خطوة بس! |
| n = 1 مليار | ~30 خطوة فقط! |
لأننا بنستخدم متغيرات ثابتة بس:
low - مؤشر البدايةhigh - مؤشر النهايةmid - مؤشر النصفمش محتاجين ذاكرة إضافية تتناسب مع حجم المصفوفة.
لو استخدمت الـ Recursive version بدل الـ Iterative، الـ Space Complexity هتبقى O(log n) بسبب الـ call stack.
جربها بنفسك!
Enter a number and click "Search" or "Step" to begin.
Logs will appear here.
الكود مع شرح كل سطر
1function binarySearch(arr, target) {
2 let low = 0;
3 let high = arr.length - 1;
4
5 while (low <= high) {
6 let mid = Math.floor((low + high) / 2);
7 let guess = arr[mid];
8
9 if (guess === target) {
10 return mid;
11 }
12 if (guess > target) {
13 high = mid - 1;
14 } else {
15 low = mid + 1;
16 }
17 }
18
19 return -1;
20}