Algoritmlar18 daqiqa
Ikkilik qidiruv (Binary Search) va Ikki ko'rsatkich (Two Pointers)
Tartiblangan massivlarda O(log N) vaqtda kerakli element yoki optimal javobni topish hamda ikki ko'rsatkich yordamida chiziqli O(N) yechimlar.
1. Ikkilik qidiruv (Binary Search) tamoyili
Agar massiv tartiblangan bo'lsa, qidiruv maydonini har qadamda ikkiga bo'lish mumkin: • Chap (left) va o'ng (right) ko'rsatkichlar o'rnatiladi. • O'rtadagi (mid) element tekshiriladi. • Agar mid qidirilayotgan qiymatdan kichik bo'lsa, chap ko'rsatkich mid + 1 ga suriladi. • Aks holda, o'ng ko'rsatkich mid - 1 ga suriladi. Vaqt murakkabligi: O(log N).
Python 3 namunasiUTF-8
def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
nums = [1, 3, 5, 7, 9, 11, 15]
print(binary_search(nums, 7)) # 3-indeks
print(binary_search(nums, 10)) # -1 (topilmadi)2. Ikki ko'rsatkich (Two Pointers) uslubi
Ikki ko'rsatkich massivning ikki chetidan (yoki bitta yo'nalishda har xil tezlikda) harakatlanib, O(N) vaqt va O(1) xotirada masalani yechish imkonini beradi. Tartiblangan massivda yig'indi target ga teng bo'lgan juftlikni topish:
Python 3 namunasiUTF-8
def two_sum_sorted(arr, target):
left, right = 0, len(arr) - 1
while left < right:
current_sum = arr[left] + arr[right]
if current_sum == target:
return [left, right]
elif current_sum < target:
left += 1
else:
right -= 1
return []
print(two_sum_sorted([2, 7, 11, 15], 9)) # [0, 1]