On a sorted row, look at the middle value. Too small, drop the left half. Too big, drop the right half. Repeat — the search space halves every step.
← Back to the Field GuideSaralangan qatorda o'rtadagi qiymatga qarang. Kichik bo'lsa — chap yarmini tashlang. Katta bo'lsa — o'ng yarmini tashlang. Har qadamda qidiruv maydoni ikkiga bo'linadi.
← Qo'llanmaga qaytishWatch the bars below: each round checks the middle of the current range and throws away the half that can't contain the target. Do that enough times and a range of thousands shrinks to one candidate in about twenty comparisons — but only because the array is sorted.
Quyidagi ustunlarga qarang: har bosqich joriy diapazonning o'rtasini tekshiradi va target bo'lishi mumkin bo'lmagan yarmini tashlab yuboradi. Buni yetarlicha takrorlasangiz, minglab elementli diapazon atigi yigirmaga yaqin solishtirishda bitta nomzodgacha qisqaradi — lekin bu faqat array saralangan bo'lgani uchun ishlaydi.
lo = 0 and hi = len(arr) - 1, marking the entire array as the current search range.lo <= hi, the range still has at least one candidate left, so compute the middle index: mid = (lo + hi) // 2 (or lo + (hi - lo) // 2 to dodge overflow — more on that below).arr[mid] to the target. If they're equal, you've found it — return mid right away.arr[mid] is less than target, the target can only be to the right (the array is sorted, so everything at or before mid is too small) — move lo = mid + 1, discarding the left half and the middle.arr[mid] is greater than target, the target can only be to the left — move hi = mid - 1, discarding the right half and the middle.[lo, hi] range. Each round the range is roughly half the size of the round before.lo ever ends up greater than hi, the range has shrunk to nothing — the target isn't in the array. Return -1.lo = 0 va hi = len(arr) - 1 — bu butun array'ni joriy qidiruv maydoni sifatida belgilaydi.lo <= hi bo'lar ekan, maydonda hali kamida bitta nomzod bor demakdir — shuning uchun o'rta indeksni hisoblang: mid = (lo + hi) // 2 (yoki overflow'dan qochish uchun lo + (hi - lo) // 2 — bu haqda pastda batafsil).arr[mid] ni target bilan solishtiring. Agar teng bo'lsa — topdingiz, darhol mid ni qaytaring.arr[mid] targetdan kichik bo'lsa, target faqat o'ngda bo'lishi mumkin (array saralangan, shuning uchun mid va undan oldingi hamma narsa juda kichik) — lo = mid + 1 qiling, chap yarmi va o'rtadagi elementni tashlab yuboring.arr[mid] targetdan katta bo'lsa, target faqat chapda bo'lishi mumkin — hi = mid - 1 qiling, o'ng yarmi va o'rtadagi elementni tashlab yuboring.[lo, hi] maydoni bilan 2-qadamga qayting. Har bosqichda maydon avvalgisining taxminan yarmiga teng bo'ladi.lo biror payt hidan katta bo'lib qolsa, maydon butunlay tugagan — target array'da yo'q. -1 qaytaring.Time: O(log n). Every comparison throws away half of whatever candidates were still left, so after k comparisons only about n / 2k elements remain in play. The search ends once that count hits zero (or one), which takes about log₂(n) comparisons — for a million-element array that's roughly 20 steps instead of up to a million for a plain linear scan. In the best case, the very first middle element you check happens to be the target, giving O(1).
Space: O(1). The iterative version shown here only ever tracks three numbers — lo, hi, and mid — no matter how large the array is; it never builds a second array or any structure that grows with the input. (A recursive version would spend O(log n) space on the call stack instead, since each recursive call waits on the stack for the one below it to return.)
Vaqt: O(log n). Har bir solishtirish qolgan nomzodlarning yarmini yo'q qiladi, shuning uchun k ta solishtirishdan keyin taxminan n / 2k ta element qoladi. Qidiruv bu son nolga (yoki bittaga) tushganda tugaydi — bu taxminan log₂(n) ta solishtirishni talab qiladi. Million elementli array uchun bu oddiy chiziqli qidiruvdagi millionga yaqin qadam o'rniga atigi 20 ga yaqin qadam degani. Eng yaxshi holatda, tekshirilgan birinchi o'rta element aynan target bo'lib chiqsa, O(1) hosil bo'ladi.
Xotira: O(1). Shu yerda ko'rsatilgan iterativ versiya array qanchalik katta bo'lishidan qat'i nazar faqat uchta sonni — lo, hi va midni — kuzatib boradi; u hech qachon ikkinchi array yoki kirish hajmiga qarab o'sadigan boshqa struktura yaratmaydi. (Rekursiv versiya esa call stack uchun O(log n) xotira sarflagan bo'lardi, chunki har bir rekursiv chaqiruv o'zidan keyingisi qaytishini stack'da kutib turadi.)
lo < hi instead of lo <= hi as the loop condition. Fix: use <= — with <, the moment exactly one candidate is left (lo == hi), the loop exits without ever checking it.mid = (lo + hi) / 2 in a language like C++ or Java, where lo and hi are fixed-width 32-bit integers: if the array is large enough that lo + hi exceeds about 2.1 billion, the addition overflows and wraps around to a negative number, producing a garbage mid. Fix: compute mid = lo + (hi - lo) / 2 instead — the intermediate value never exceeds hi, so it can't overflow. Python doesn't have this problem at all: its integers have arbitrary precision and grow automatically as needed, so lo + hi can never overflow no matter how large the numbers get — but writing lo + (hi - lo) // 2 is still a fine habit if you ever port the code to C++ or Java.hi = mid or lo = mid instead of mid - 1 / mid + 1. Fix: always exclude mid itself once it's been checked and ruled out — leaving it in the range risks comparing the same element forever and looping infinitely.-1 for a value that's really there, because the "discard half" logic assumes an order that doesn't exist. Fix: sort the data first, or reach for a different algorithm if sorting isn't an option.lo <= hi o'rniga lo < hi deb yozish. Yechim: <= dan foydalaning — < bilan, aynan bitta nomzod qolganda (lo == hi), loop uni umuman tekshirmasdan tugaydi.mid = (lo + hi) / 2 deb yozish — bu yerda lo va hi qat'iy 32-bitli butun sonlar: agar array yetarlicha katta bo'lib, lo + hi taxminan 2.1 milliarddan oshsa, qo'shish overflow bo'ladi va manfiy songa aylanib, noto'g'ri mid beradi. Yechim: buning o'rniga mid = lo + (hi - lo) / 2 ni hisoblang — bu oraliq qiymat hech qachon hidan oshmaydi, shuning uchun overflow bo'lolmaydi. Python'da bu muammo umuman yo'q: uning butun sonlari arbitrary-precision — ular kerak bo'lganda avtomatik o'sadi, shuning uchun lo + hi qanchalik katta bo'lishidan qat'i nazar hech qachon overflow bo'lmaydi — lekin kodni C++ yoki Java'ga ko'chirsangiz, lo + (hi - lo) // 2 deb yozish baribir yaxshi odat.mid - 1 / mid + 1 o'rniga hi = mid yoki lo = mid deb qisqartirish. Yechim: tekshirilib, rad etilgan midni har doim maydondan chiqarib tashlang — uni qoldirish xuddi shu elementni cheksiz solishtirish va cheksiz loop xavfini tug'diradi.-1 qaytaradi, chunki "yarmini tashlash" mantig'i mavjud bo'lmagan tartibni taxmin qiladi. Yechim: avval ma'lumotni saralang, yoki saralash imkoni bo'lmasa boshqa algoritmga murojaat qiling.mid has to be cheap, or the whole speed advantage disappears (a linked list, where reaching the middle costs O(n) itself, is a bad fit).mid indeksiga to'g'ridan-to'g'ri sakrash arzon bo'lishi kerak, aks holda butun tezlik ustunligi yo'qoladi (linked list, unda o'rtaga yetib borish o'zi O(n) turadi, bu yerga mos kelmaydi).Restated: given an integer array nums sorted in ascending order and an integer target, return the index of target in nums if it exists, or -1 if it doesn't — and do it in O(log n) time.
lo, hi = 0, len(nums) - 1 covers the whole array — every index is still a candidate before the first comparison.while lo <= hi: — compute mid, then compare nums[mid] against target.mid. Too small → lo = mid + 1. Too big → hi = mid - 1. Each branch keeps the sorted-order guarantee intact for whatever range is left.lo has crossed past hi, meaning every candidate has been eliminated — return -1.def search(nums, target):
lo, hi = 0, len(nums) - 1
while lo <= hi:
mid = lo + (hi - lo) // 2 # avoids the C++/Java overflow trap (harmless in Python too)
if nums[mid] == target:
return mid # found it, return the index
elif nums[mid] < target:
lo = mid + 1 # target must be to the right, discard mid and everything left of it
else:
hi = mid - 1 # target must be to the left, discard mid and everything right of it
return -1 # lo > hi: range emptied out, target isn't in nums
Qayta bayon: o'sish tartibida saralangan butun sonlar array'i nums va butun son target berilgan — agar target numsda mavjud bo'lsa uning indeksini, aks holda -1 ni qaytaring, va buni O(log n) vaqtda bajaring.
lo, hi = 0, len(nums) - 1 butun array'ni qamrab oladi — birinchi solishtirishdan oldin har bir index hali nomzod hisoblanadi.while lo <= hi: — midni hisoblang, so'ng nums[mid] ni target bilan solishtiring.midni qaytaring. Juda kichik → lo = mid + 1. Juda katta → hi = mid - 1. Har bir tarmoq qolgan maydon uchun saralangan tartib kafolatini saqlab qoladi.lo allaqachon hidan oshib ketgan bo'ladi — bu barcha nomzodlar yo'qqa chiqarilganini bildiradi — -1 qaytaring.def search(nums, target):
lo, hi = 0, len(nums) - 1
while lo <= hi:
mid = lo + (hi - lo) // 2 # avoids the C++/Java overflow trap (harmless in Python too)
if nums[mid] == target:
return mid # found it, return the index
elif nums[mid] < target:
lo = mid + 1 # target must be to the right, discard mid and everything left of it
else:
hi = mid - 1 # target must be to the left, discard mid and everything right of it
return -1 # lo > hi: range emptied out, target isn't in nums
arr[mid] to the target and assuming everything on one side is smaller and everything on the other is larger. That assumption is only true because the array is sorted — on unsorted data, the "wrong" half could easily contain the target, and discarding it would silently produce a wrong answer.lo and hi are fixed-width 32-bit integers in C++/Java; if both are large, their sum can exceed roughly 2.1 billion and overflow, wrapping around to a negative number and producing a broken mid. The fix is mid = lo + (hi - lo) / 2, which never lets the intermediate value exceed hi. Python sidesteps the whole problem: its integers have arbitrary precision and grow automatically as needed, so lo + hi can never overflow no matter how large the numbers get.arr[mid] ni target bilan solishtirish va bir tarafdagi hamma narsa kichikroq, ikkinchi tarafdagi hamma narsa kattaroq deb taxmin qilish orqali hal qilinadi. Bu taxmin faqat array saralangani uchun to'g'ri — saralanmagan ma'lumotda "noto'g'ri" yarim osongina target'ni o'z ichiga olishi mumkin, va uni tashlab yuborish sezilmagan holda noto'g'ri javob berib qo'yadi.lo va hi qat'iy 32-bitli butun sonlar; ikkalasi ham katta bo'lsa, ularning yig'indisi taxminan 2.1 milliarddan oshib overflow bo'lishi, manfiy songa aylanib, buzuq mid berishi mumkin. Yechim — mid = lo + (hi - lo) / 2, bu oraliq qiymatni hech qachon hidan oshirmaydi. Python bu muammoni butunlay chetlab o'tadi: uning butun sonlari arbitrary-precision — kerak bo'lganda avtomatik o'sadi, shuning uchun lo + hi sonlar qanchalik katta bo'lishidan qat'i nazar hech qachon overflow bo'lmaydi.