Tarkibga o'tish

9-bo'lim: Qidiruv

↑ Mundarijaga qaytish

⚠️ Ikkilik qidiruv (binary search) saralangan massiv talab qiladi. Saralanmagan ma'lumotda faqat chiziqli qidiruv ishlaydi.

⏱ O(n) Β· πŸ’Ύ O(1) β€” topilmasa βˆ’1.

JS 

const linearSearch = (arr, x) => {
  for (let i = 0; i < arr.length; i++) if (arr[i] === x) return i;
  return -1;
};
PHP 
function linearSearch($arr, $x) {
    foreach ($arr as $i => $v) if ($v === $x) return $i;
    return -1;
}
Python 
def linear_search(arr, x):
    for i, v in enumerate(arr):
        if v == x:
            return i
    return -1

114. Ikkilik qidiruv β€” iterativ

⏱ O(log n) Β· πŸ’Ύ O(1) JS'da (lo + hi) >> 1 butun bo'lishni ta'minlaydi.

JS 

const binarySearch = (arr, x) => {
  let lo = 0, hi = arr.length - 1;
  while (lo <= hi) {
    const mid = (lo + hi) >> 1;
    if (arr[mid] === x) return mid;
    if (arr[mid] < x) lo = mid + 1;
    else hi = mid - 1;
  }
  return -1;
};
PHP 
function binarySearch($arr, $x) {
    $lo = 0;
    $hi = count($arr) - 1;
    while ($lo <= $hi) {
        $mid = intdiv($lo + $hi, 2);
        if ($arr[$mid] === $x) return $mid;
        if ($arr[$mid] < $x) $lo = $mid + 1;
        else $hi = $mid - 1;
    }
    return -1;
}
Python 
def binary_search(arr, x):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if arr[mid] == x:
            return mid
        if arr[mid] < x:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

Har qadamda o'rta (mid) tekshirilib, qidiruv oralig'i yarmiga qisqarishini quyidagi diagrammada kuzating:

Ikkilik qidiruv: har qadamda o'rtani tekshirib, oraliqni yarmiga bo'lish

115. Ikkilik qidiruv β€” rekursiv

⏱ O(log n) Β· πŸ’Ύ O(log n) β€” stek.

JS 

const binarySearchRec = (arr, x, lo = 0, hi = arr.length - 1) => {
  if (lo > hi) return -1;
  const mid = (lo + hi) >> 1;
  if (arr[mid] === x) return mid;
  return arr[mid] < x
    ? binarySearchRec(arr, x, mid + 1, hi)
    : binarySearchRec(arr, x, lo, mid - 1);
};
PHP 
function binarySearchRec($arr, $x, $lo = 0, $hi = null) {
    if ($hi === null) $hi = count($arr) - 1;
    if ($lo > $hi) return -1;
    $mid = intdiv($lo + $hi, 2);
    if ($arr[$mid] === $x) return $mid;
    return $arr[$mid] < $x
        ? binarySearchRec($arr, $x, $mid + 1, $hi)
        : binarySearchRec($arr, $x, $lo, $mid - 1);
}
Python 
def binary_search_rec(arr, x, lo=0, hi=None):
    if hi is None:
        hi = len(arr) - 1
    if lo > hi:
        return -1
    mid = (lo + hi) // 2
    if arr[mid] == x:
        return mid
    if arr[mid] < x:
        return binary_search_rec(arr, x, mid + 1, hi)
    return binary_search_rec(arr, x, lo, mid - 1)

116. Birinchi uchrashi (leftmost)

⏱ O(log n) Β· πŸ’Ύ O(1) Takrorlanuvchi qiymatlar bo'lgan saralangan massivda x'ning eng chap indeksi.

JS 

const firstOccurrence = (arr, x) => {
  let lo = 0, hi = arr.length - 1, res = -1;
  while (lo <= hi) {
    const mid = (lo + hi) >> 1;
    if (arr[mid] === x) { res = mid; hi = mid - 1; }
    else if (arr[mid] < x) lo = mid + 1;
    else hi = mid - 1;
  }
  return res;
};
PHP 
function firstOccurrence($arr, $x) {
    $lo = 0; $hi = count($arr) - 1; $res = -1;
    while ($lo <= $hi) {
        $mid = intdiv($lo + $hi, 2);
        if ($arr[$mid] === $x) { $res = $mid; $hi = $mid - 1; }
        elseif ($arr[$mid] < $x) $lo = $mid + 1;
        else $hi = $mid - 1;
    }
    return $res;
}
Python 
def first_occurrence(arr, x):
    lo, hi, res = 0, len(arr) - 1, -1
    while lo <= hi:
        mid = (lo + hi) // 2
        if arr[mid] == x:
            res = mid
            hi = mid - 1
        elif arr[mid] < x:
            lo = mid + 1
        else:
            hi = mid - 1
    return res

117. Oxirgi uchrashi (rightmost)

⏱ O(log n) Β· πŸ’Ύ O(1) Birinchi + oxirgi indeks orqali element nechta marta uchrashini O(log n) da topish mumkin.

JS 

const lastOccurrence = (arr, x) => {
  let lo = 0, hi = arr.length - 1, res = -1;
  while (lo <= hi) {
    const mid = (lo + hi) >> 1;
    if (arr[mid] === x) { res = mid; lo = mid + 1; }
    else if (arr[mid] < x) lo = mid + 1;
    else hi = mid - 1;
  }
  return res;
};
PHP 
function lastOccurrence($arr, $x) {
    $lo = 0; $hi = count($arr) - 1; $res = -1;
    while ($lo <= $hi) {
        $mid = intdiv($lo + $hi, 2);
        if ($arr[$mid] === $x) { $res = $mid; $lo = $mid + 1; }
        elseif ($arr[$mid] < $x) $lo = $mid + 1;
        else $hi = $mid - 1;
    }
    return $res;
}
Python 
def last_occurrence(arr, x):
    lo, hi, res = 0, len(arr) - 1, -1
    while lo <= hi:
        mid = (lo + hi) // 2
        if arr[mid] == x:
            res = mid
            lo = mid + 1
        elif arr[mid] < x:
            lo = mid + 1
        else:
            hi = mid - 1
    return res

118. Kiritish nuqtasi (lower bound)

⏱ O(log n) Β· πŸ’Ύ O(1) x'ni tartibni buzmasdan joylash mumkin bo'lgan eng kichik indeks. Pythonda bisect moduli shu ishni qiladi.

JS 

const lowerBound = (arr, x) => {
  let lo = 0, hi = arr.length;
  while (lo < hi) {
    const mid = (lo + hi) >> 1;
    if (arr[mid] < x) lo = mid + 1;
    else hi = mid;
  }
  return lo;
};
PHP 
function lowerBound($arr, $x) {
    $lo = 0; $hi = count($arr);
    while ($lo < $hi) {
        $mid = intdiv($lo + $hi, 2);
        if ($arr[$mid] < $x) $lo = $mid + 1;
        else $hi = $mid;
    }
    return $lo;
}
Python 
import bisect

def lower_bound(arr, x):
    return bisect.bisect_left(arr, x)

119. Aylantirilgan saralangan massivda qidiruv

⏱ O(log n) Β· πŸ’Ύ O(1) Mas. [4,5,6,7,0,1,2]. Har qadamda yarmi tartibli β€” shuni aniqlab, qidiruvni to'g'ri yarmiga yo'naltiramiz.

JS 

const searchRotated = (arr, x) => {
  let lo = 0, hi = arr.length - 1;
  while (lo <= hi) {
    const mid = (lo + hi) >> 1;
    if (arr[mid] === x) return mid;
    if (arr[lo] <= arr[mid]) {
      if (arr[lo] <= x && x < arr[mid]) hi = mid - 1;
      else lo = mid + 1;
    } else {
      if (arr[mid] < x && x <= arr[hi]) lo = mid + 1;
      else hi = mid - 1;
    }
  }
  return -1;
};
PHP 
function searchRotated($arr, $x) {
    $lo = 0; $hi = count($arr) - 1;
    while ($lo <= $hi) {
        $mid = intdiv($lo + $hi, 2);
        if ($arr[$mid] === $x) return $mid;
        if ($arr[$lo] <= $arr[$mid]) {
            if ($arr[$lo] <= $x && $x < $arr[$mid]) $hi = $mid - 1;
            else $lo = $mid + 1;
        } else {
            if ($arr[$mid] < $x && $x <= $arr[$hi]) $lo = $mid + 1;
            else $hi = $mid - 1;
        }
    }
    return -1;
}
Python 
def search_rotated(arr, x):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if arr[mid] == x:
            return mid
        if arr[lo] <= arr[mid]:
            if arr[lo] <= x < arr[mid]:
                hi = mid - 1
            else:
                lo = mid + 1
        else:
            if arr[mid] < x <= arr[hi]:
                lo = mid + 1
            else:
                hi = mid - 1
    return -1

120. Butun kvadrat ildiz (integer sqrt)

⏱ O(log n) Β· πŸ’Ύ O(1) "Javob bo'yicha ikkilik qidiruv" (binary search on answer) namunasi β€” floor(√n). Pythonda math.isqrt(n) ham bor.

JS 

const intSqrt = n => {
  if (n < 2) return n;
  let lo = 1, hi = n, res = 0;
  while (lo <= hi) {
    const mid = (lo + hi) >> 1;
    if (mid * mid <= n) { res = mid; lo = mid + 1; }
    else hi = mid - 1;
  }
  return res;
};
PHP 
function intSqrt($n) {
    if ($n < 2) return $n;
    $lo = 1; $hi = $n; $res = 0;
    while ($lo <= $hi) {
        $mid = intdiv($lo + $hi, 2);
        if ($mid * $mid <= $n) { $res = $mid; $lo = $mid + 1; }
        else $hi = $mid - 1;
    }
    return $res;
}
Python 
def int_sqrt(n):
    if n < 2:
        return n
    lo, hi, res = 1, n, 0
    while lo <= hi:
        mid = (lo + hi) // 2
        if mid * mid <= n:
            res = mid
            lo = mid + 1
        else:
            hi = mid - 1
    return res