# Binary Search: Algoritm dunyosining eng muhim qidiruv usulidan tortib murakkab variatsiyalargacha Binary Search - bu algoritm olamidagi eng muhim va fundamental qidiruv algoritmlaridan biri. Agar siz dasturlashni o'rganayotgan bo'lsangiz yoki senior developer bo'lsangiz ham, Binary Search algoritmi sizning arsenal'ingizda eng keskin qurollardan biri bo'lishi kerak. Bu maqolada biz Binary Search algoritmini 0 dan boshlab, uning barcha variatsiyalari va real hayotdagi qo'llanishlari bilan birga chuqur o'rganamiz. > [!IMPORTANT] > Bu maqola sizga nafaqat Binary Search kodini yozishni, balki uning matematik mohiyatini, murakkablik tahlilini va eng muhimi - qachon va qanday ishlatishni to'liq o'rgatadi. ## Binary Search nima va nega bu qadar muhim? Binary Search algoritmining mohiyatini tushunish uchun avval oddiy hayotiy misoldan boshlaymiz. Tasavvur qiling, sizda 1 dan 1000 gacha raqamlardan tashkil topgan kitob bor va siz ma'lum bir sahifani topishingiz kerak. Eng oddiy usul - sahifalarni boshidan oxirigacha varaqlab chiqish. Lekin bu juda samarasiz! ### Hayotiy misol: Lug'atdan so'z qidirish Lug'atdan so'z qidirayotganda siz quyidagi algoritmdan foydalanasiz: 1. **Lug'atni o'rtasidan ochib ko'rasiz** - masalan, M harfidagi so'zlar ko'rinadi 2. **Qidirayotgan so'z (masalan, "Apple") M dan oldinmi yoki keyin ekanligini tekshirasiz** 3. **Agar oldin bo'lsa, lug'atning chap yarmini tanlab, yana o'rtasini ochasiz** 4. **Bu jarayonni qidirayotgan so'z topilguncha davom ettirasiz** Bu jarayon aynan Binary Search algoritmidir! Har bir qadamda qidiruv maydonini ikki baravarga kamaytiramiz. ```mermaid flowchart TD A["Tartiblangan array: [1,3,5,7,9,11,13,15,17,19"] Target: 13"] --> B{"O'rta element: arr[4] = 9"} B --> C["Target - 13 > 9 O'ng yarimda qidiramiz"] B --> D["Target - 13 < 9 Chap yarimda qidiramiz"] B --> E["Target - 13 = 9 TOPILDI!"] C --> F["Yangi range: [11,13,15,17,19"] O'rta: arr[7] = 15"] F --> G["Target - 13 < 15 Chap yarimda qidiramiz"] G --> H["Yangi range: [11,13"] O'rta: arr[6] = 13"] H --> I["Target - 13 = 13 TOPILDI! Index: 6"] style I fill:#90EE90 style A fill:#E6E6FA style H fill:#FFE4B5 ``` ### Matematik asoslar va Time Complexity chuqur tahlili Binary Search algoritmining kuchi uning matematik asosida yotadi. Har bir qadamda qidiruv maydonini yarimga kamaytiramiz. Bu logarifmik vaqt murakkabligini beradi. #### Matematik formular va isbotlash **Time Complexity: O(log₂ n)** Isboti: - Har bir iteratsiyada array hajmi ikki baravarga kamayadi - n elementli arraydan boshlab: n → n/2 → n/4 → n/8 → ... → 1 - Bu jarayon maksimal ⌊log₂ n⌋ + 1 marta takrorlanadi - Demak, time complexity O(log n) **Space Complexity:** - Iterativ implementatsiya uchun: **O(1)** - Rekursiv implementatsiya uchun: **O(log n)** (call stack tufayli) #### Amaliy murakkablik taqqoslash jadvali | Array hajmi (n) | Binary Search qadamlar | Linear Search qadamlar | Tezlik farqi | | ----------------- | ------------------------ | ------------------------ | -------------- | | 10 | 4 | 10 | 2.5x | | 100 | 7 | 100 | 14.3x | | 1,000 | 10 | 1,000 | 100x | | 10,000 | 14 | 10,000 | 714x | | 100,000 | 17 | 100,000 | 5,882x | | 1,000,000 | 20 | 1,000,000 | 50,000x | | 10,000,000 | 24 | 10,000,000 | 416,667x | | 1,000,000,000 | 30 | 1,000,000,000 | 33,333,333x | > [!NOTE] > Ko'rib turganingizdek, ma'lumotlar hajmi oshgan sari Binary Search'ning ustunligi dramatik tarzda oshadi. 1 milliard elementli arrayda ham maksimal 30 ta qadamda javobni topadi! #### Logarifmning amaliy ma'nosi Logarifm - bu "qancha marta 2 ga bo'lish mumkin?" degan savolga javob: ```javascript function explainLogarithm(n) { let steps = 0; let current = n; console.log(`${n} elementli arrayda Binary Search jarayoni:`); while (current > 1) { current = Math.floor(current / 2); steps++; console.log(`Qadam ${steps}: ${current} element qoldi`); } console.log(`Jami qadamlar: ${steps} ≈ log₂(${n}) = ${Math.ceil(Math.log2(n))}`); return steps; } // Misollar explainLogarithm(1000); explainLogarithm(1000000); ``` Bu funksiya ishlaganda: ```text 1000 elementli arrayda Binary Search jarayoni: Qadam 1: 500 element qoldi Qadam 2: 250 element qoldi Qadam 3: 125 element qoldi Qadam 4: 62 element qoldi Qadam 5: 31 element qoldi Qadam 6: 15 element qoldi Qadam 7: 7 element qoldi Qadam 8: 3 element qoldi Qadam 9: 1 element qoldi Jami qadamlar: 9 ≈ log₂(1000) = 10 ``` ### Binary Search uchun asosiy shartlar va cheklovlar Binary Search ishlashi uchun quyidagi shartlar bajarilishi shart: #### 1. Asosiy shart: Ma'lumotlar tartiblangan bo'lishi ```javascript // ✅ TO'G'RI - tartiblangan array const sortedArray = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]; // ❌ NOTO'G'RI - tartiblanmagan array const unsortedArray = [3, 1, 7, 15, 9, 5, 19, 11, 13, 17]; // Tartiblanganlikni tekshirish funksiyasi function isSorted(arr, ascending = true) { for (let i = 1; i < arr.length; i++) { if (ascending) { if (arr[i] < arr[i-1]) return false; } else { if (arr[i] > arr[i-1]) return false; } } return true; } console.log(isSorted(sortedArray)); // true console.log(isSorted(unsortedArray)); // false ``` #### 2. Random Access qo'llab-quvvatlash Binary Search faqat random access qo'llab-quvvatlaydigan ma'lumotlar tuzilmalarida ishlaydi (arrays, vectors). Linked list'larda ishlamaydi, chunki o'rta elementga O(1) vaqtda kirish mumkin emas. ```javascript // Array uchun - ✅ TO'G'RI const array = [1, 2, 3, 4, 5]; const midElement = array[Math.floor(array.length / 2)]; // O(1) // Linked List uchun - ❌ SAMARASIZ class ListNode { constructor(val, next = null) { this.val = val; this.next = next; } } function getMiddleOfLinkedList(head) { // O(n/2) vaqt kerak - Binary Search uchun samarasiz let slow = head; let fast = head; while (fast && fast.next) { slow = slow.next; fast = fast.next.next; } return slow.val; } ``` #### 3. Elementlarni solishtirish imkoniyati Elementlar o'rtasida tartib munosabati (comparison) mavjud bo'lishi kerak: ```javascript // Raqamlar uchun - oddiy function compareNumbers(a, b) { if (a < b) return -1; if (a > b) return 1; return 0; } // String'lar uchun function compareStrings(a, b) { return a.localeCompare(b); } // Obyektlar uchun - custom comparator kerak function compareObjects(a, b, key) { if (a[key] < b[key]) return -1; if (a[key] > b[key]) return 1; return 0; } const people = [ {name: "Alice", age: 25}, {name: "Bob", age: 30}, {name: "Charlie", age: 35} ]; // Age bo'yicha qidirish function binarySearchPeople(arr, targetAge) { let left = 0; let right = arr.length - 1; while (left <= right) { const mid = left + Math.floor((right - left) / 2); const midAge = arr[mid].age; if (midAge === targetAge) { return mid; } if (targetAge < midAge) { right = mid - 1; } else { left = mid + 1; } } return -1; } ``` > [!WARNING] > Binary Search algoritmini tartiblanmagan arrayda qo'llash xatolikka olib keladi va noto'g'ri natija beradi. Bunday holatlarda avval arrayni tartiblash (O(n log n)) yoki Linear Search (O(n)) ishlatish kerak. #### 4. Array hajmi ma'lum bo'lishi Binary Search array'ning oxirgi indeksini bilishni talab qiladi. Bu har doim ham trivial emas: ```javascript // Oddiy array uchun const arr = [1, 2, 3, 4, 5]; const lastIndex = arr.length - 1; // 4 // Infinite array yoki stream uchun - exponential search kerak function binarySearchInInfiniteArray(arr, target) { // Avval array oxirini topish (exponential search) let bound = 1; while (bound < arr.length && arr[bound] < target) { bound *= 2; } // Endi binary search let left = bound / 2; let right = Math.min(bound, arr.length - 1); while (left <= right) { const mid = left + Math.floor((right - left) / 2); if (arr[mid] === target) { return mid; } if (target < arr[mid]) { right = mid - 1; } else { left = mid + 1; } } return -1; } ``` ## Klassik Binary Search implementatsiyasi Endi Binary Search algoritmini har xil usullarda implement qilamiz va har bir yondashuvning chuqur tahlilini qilamiz. ### Iterativ implementatsiya - Professional darajada Iterativ yondashuv production code'da eng ko'p ishlatiladi, chunki u memory efficient va stack overflow xavfi yo'q: ```javascript /** * Klassik Binary Search - Iterativ implementatsiya * @param {number[]} arr - Tartiblangan array * @param {number} target - Qidirilayotgan element * @returns {number} - Element topilgan indeks yoki -1 * Time Complexity: O(log n) * Space Complexity: O(1) */ function binarySearchIterative(arr, target) { // Input validation if (!arr || arr.length === 0) { return -1; } let left = 0; // Chap chegara (inclusive) let right = arr.length - 1; // O'ng chegara (inclusive) // Loop invariant: agar target mavjud bo'lsa, u [left, right] oralig'ida while (left <= right) { // O'rta indeksni hisoblash - overflow'dan qochish uchun bu usul // C++ yoki Java'da muhim, JavaScript'da unchalik emas const mid = left + Math.floor((right - left) / 2); const midValue = arr[mid]; // Target topildi if (midValue === target) { return mid; } // Target chap yarimda if (target < midValue) { right = mid - 1; // mid'ni chiqarib tashlaymiz } // Target o'ng yarimda else { left = mid + 1; // mid'ni chiqarib tashlaymiz } } // Element topilmadi return -1; } // Enhanced version with debugging information function binarySearchWithDebug(arr, target) { console.log(`🔍 Qidirilayotgan: ${target}`); console.log(`📊 Array: [${arr.join(', ')}]`); console.log('━'.repeat(50)); let left = 0; let right = arr.length - 1; let iteration = 1; while (left <= right) { const mid = left + Math.floor((right - left) / 2); const midValue = arr[mid]; console.log(`Iteratsiya ${iteration}:`); console.log(` Range: [${left}, ${right}]`); console.log(` Mid index: ${mid}, Mid value: ${midValue}`); if (midValue === target) { console.log(` ✅ TOPILDI! Index: ${mid}`); return mid; } if (target < midValue) { console.log(` ⬅️ ${target} < ${midValue}, chap yarimda qidiramiz`); right = mid - 1; } else { console.log(` ➡️ ${target} > ${midValue}, o'ng yarimda qidiramiz`); left = mid + 1; } console.log(` Yangi range: [${left}, ${right}]`); console.log(''); iteration++; } console.log(`❌ Element topilmadi`); return -1; } // Test qilish const testArray = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25]; console.log("=== BINARY SEARCH DEMO ==="); binarySearchWithDebug(testArray, 13); console.log("\n" + "=".repeat(50) + "\n"); binarySearchWithDebug(testArray, 8); ``` ### Rekursiv implementatsiya - Matematik jihatdan mukammal Rekursiv yondashuv matematik jihatdan yanada intuitiv va divide-and-conquer printsipini aks ettiradi: ```javascript /** * Binary Search - Rekursiv implementatsiya * @param {number[]} arr - Tartiblangan array * @param {number} target - Qidirilayotgan element * @param {number} left - Chap chegara (default: 0) * @param {number} right - O'ng chegara (default: arr.length - 1) * @returns {number} - Element topilgan indeks yoki -1 * Time Complexity: O(log n) * Space Complexity: O(log n) - call stack tufayli */ function binarySearchRecursive(arr, target, left = 0, right = arr.length - 1) { // Base case: qidiruv oralig'i bo'sh if (left > right) { return -1; } // O'rta nuqtani hisoblash const mid = left + Math.floor((right - left) / 2); const midValue = arr[mid]; // Base case: element topildi if (midValue === target) { return mid; } // Rekursiv case: chap yarimda qidiramiz if (target < midValue) { return binarySearchRecursive(arr, target, left, mid - 1); } // Rekursiv case: o'ng yarimda qidiramiz return binarySearchRecursive(arr, target, mid + 1, right); } // Call stack'ni ko'rsatadigan versiya function binarySearchRecursiveWithStack(arr, target, left = 0, right = arr.length - 1, depth = 0) { const indent = ' '.repeat(depth); console.log(`${indent}📞 Call ${depth + 1}: range[${left}, ${right}]`); // Base case: qidiruv oralig'i bo'sh if (left > right) { console.log(`${indent}❌ Base case: left > right, return -1`); return -1; } const mid = left + Math.floor((right - left) / 2); const midValue = arr[mid]; console.log(`${indent}🎯 Mid: index=${mid}, value=${midValue}`); // Base case: element topildi if (midValue === target) { console.log(`${indent}✅ Found at index ${mid}!`); return mid; } // Rekursiv case if (target < midValue) { console.log(`${indent}⬅️ Searching left half`); return binarySearchRecursiveWithStack(arr, target, left, mid - 1, depth + 1); } else { console.log(`${indent}➡️ Searching right half`); return binarySearchRecursiveWithStack(arr, target, mid + 1, right, depth + 1); } } // Test qilish console.log("=== REKURSIV BINARY SEARCH DEMO ==="); const numbers = [2, 4, 6, 8, 10, 12, 14, 16, 18, 20]; binarySearchRecursiveWithStack(numbers, 12); ``` ### Template-based Binary Search Professional development'da ko'pincha umumiy template ishlatiladi: ```javascript /** * Universal Binary Search Template * Bu template ko'p xil binary search variatsiyalari uchun ishlatilishi mumkin */ class BinarySearchTemplate { /** * Asosiy binary search template * @param {number} left - Chap chegara * @param {number} right - O'ng chegara * @param {Function} condition - Shart funksiyasi * @returns {number} - Natija indeksi */ static search(left, right, condition) { while (left < right) { const mid = left + Math.floor((right - left) / 2); if (condition(mid)) { right = mid; } else { left = mid + 1; } } return left; } /** * Klassik binary search */ static findTarget(arr, target) { const index = this.search(0, arr.length, (mid) => arr[mid] >= target); return (index < arr.length && arr[index] === target) ? index : -1; } /** * Lower bound (birinchi >= target element) */ static lowerBound(arr, target) { return this.search(0, arr.length, (mid) => arr[mid] >= target); } /** * Upper bound (birinchi > target element) */ static upperBound(arr, target) { return this.search(0, arr.length, (mid) => arr[mid] > target); } /** * Square root hisoblash */ static sqrt(x) { if (x === 0) return 0; return this.search(1, x + 1, (mid) => mid * mid > x) - 1; } } // Test qilish const testArr = [1, 2, 2, 3, 3, 3, 4, 5, 5, 6]; console.log("=== TEMPLATE BINARY SEARCH DEMO ==="); console.log(`Array: [${testArr.join(', ')}]`); console.log(`Find 3: ${BinarySearchTemplate.findTarget(testArr, 3)}`); console.log(`Lower bound of 3: ${BinarySearchTemplate.lowerBound(testArr, 3)}`); console.log(`Upper bound of 3: ${BinarySearchTemplate.upperBound(testArr, 3)}`); console.log(`Square root of 16: ${BinarySearchTemplate.sqrt(16)}`); console.log(`Square root of 15: ${BinarySearchTemplate.sqrt(15)}`); ``` ### Binary Search algoritmi ishlashining detailed tahlili Algoritm ishlash jarayonini visualization bilan ko'rib chiqaylik: ```javascript class BinarySearchVisualizer { constructor(arr, target) { this.arr = arr; this.target = target; this.steps = []; } search() { let left = 0; let right = this.arr.length - 1; let step = 1; while (left <= right) { const mid = left + Math.floor((right - left) / 2); // Har bir qadamni saqlash this.steps.push({ step: step, left: left, right: right, mid: mid, midValue: this.arr[mid], comparison: this.getComparison(this.arr[mid]), searchSpace: this.arr.slice(left, right + 1) }); if (this.arr[mid] === this.target) { this.steps[this.steps.length - 1].found = true; return mid; } if (this.target < this.arr[mid]) { right = mid - 1; } else { left = mid + 1; } step++; } return -1; } getComparison(midValue) { if (this.target === midValue) return 'EQUAL'; return this.target < midValue ? 'LESS' : 'GREATER'; } visualize() { console.log(`🔍 Binary Search Visualization`); console.log(`Array: [${this.arr.join(', ')}]`); console.log(`Target: ${this.target}`); console.log('═'.repeat(80)); const result = this.search(); this.steps.forEach(step => { console.log(`\n📍 Step ${step.step}:`); console.log(` Range: [${step.left}, ${step.right}] → [${step.searchSpace.join(', ')}]`); console.log(` Mid: index=${step.mid}, value=${step.midValue}`); if (step.found) { console.log(` 🎉 FOUND! Target ${this.target} at index ${step.mid}`); } else { const arrow = step.comparison === 'LESS' ? '⬅️' : '➡️'; const direction = step.comparison === 'LESS' ? 'left' : 'right'; console.log(` ${arrow} ${this.target} ${step.comparison === 'LESS' ? '<' : '>'} ${step.midValue}, search ${direction}`); } }); if (result === -1) { console.log(`\n❌ Target ${this.target} not found in array`); } console.log(`\n📊 Statistics:`); console.log(` Total steps: ${this.steps.length}`); console.log(` Theoretical max steps: ${Math.ceil(Math.log2(this.arr.length))}`); console.log(` Efficiency: ${((Math.ceil(Math.log2(this.arr.length)) - this.steps.length) / Math.ceil(Math.log2(this.arr.length)) * 100).toFixed(1)}% better than worst case`); return result; } // ASCII art visualization visualizeArray() { console.log('\n🎨 Array Visualization:'); this.steps.forEach((step, index) => { console.log(`\nStep ${step.step}:`); // Array ko'rinishi let arrayStr = ''; for (let i = 0; i < this.arr.length; i++) { if (i === step.mid) { arrayStr += `[${this.arr[i].toString().padStart(2)}]`; } else if (i >= step.left && i <= step.right) { arrayStr += ` ${this.arr[i].toString().padStart(2)} `; } else { arrayStr += ' - '; } } console.log(`Array: ${arrayStr}`); // Pointer'lar let pointerStr = ''; for (let i = 0; i < this.arr.length; i++) { if (i === step.mid) { pointerStr += ' ↑M '; } else if (i === step.left) { pointerStr += ' ↑L '; } else if (i === step.right) { pointerStr += ' ↑R '; } else { pointerStr += ' '; } } console.log(` ${pointerStr}`); }); } } // Demo console.log("=== BINARY SEARCH DETAILED VISUALIZATION ==="); const visualArray = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29]; const visualizer = new BinarySearchVisualizer(visualArray, 17); visualizer.visualize(); visualizer.visualizeArray(); ``` ### Performance Testing va Benchmark Binary Search'ning real performance'ini o'lchab ko'ramiz: ```javascript class BinarySearchBenchmark { static generateSortedArray(size) { const arr = []; for (let i = 0; i < size; i++) { arr.push(i * 2 + 1); // Toq raqamlar } return arr; } static linearSearch(arr, target) { for (let i = 0; i < arr.length; i++) { if (arr[i] === target) { return i; } } return -1; } static binarySearch(arr, target) { let left = 0; let right = arr.length - 1; while (left <= right) { const mid = left + Math.floor((right - left) / 2); if (arr[mid] === target) { return mid; } if (target < arr[mid]) { right = mid - 1; } else { left = mid + 1; } } return -1; } static benchmark(sizes = [1000, 10000, 100000, 1000000]) { console.log('🏃‍♂️ Binary Search vs Linear Search Performance Test'); console.log('═'.repeat(80)); const results = []; sizes.forEach(size => { const arr = this.generateSortedArray(size); const target = arr[Math.floor(arr.length * 0.75)]; // 75% joyda const iterations = 1000; // Linear Search benchmark const linearStart = performance.now(); for (let i = 0; i < iterations; i++) { this.linearSearch(arr, target); } const linearTime = performance.now() - linearStart; // Binary Search benchmark const binaryStart = performance.now(); for (let i = 0; i < iterations; i++) { this.binarySearch(arr, target); } const binaryTime = performance.now() - binaryStart; const speedup = (linearTime / binaryTime).toFixed(2); results.push({ size, linearTime: linearTime.toFixed(3), binaryTime: binaryTime.toFixed(3), speedup }); console.log(`📊 Array size: ${size.toLocaleString()}`); console.log(` Linear Search: ${linearTime.toFixed(3)}ms`); console.log(` Binary Search: ${binaryTime } } } } ```