Ufak bir işlem sonrası sıralanmış dizinin bazı elemanlarının yerleri karıştırılıyor. Örneğin i.
pozisyonda olması gereken eleman i-1
ya da i+1
pozisyonunda bulunuyor. Hedef olarak verilen sayının dizi içerisindeki pozisyonunun bulunması amaçlanıyor.
Örneğin;
Input: arr[] = {10, 3, 40, 20, 50, 80, 70}, key = 40
Output: 2
Input: arr[] = {10, 3, 40, 20, 50, 80, 70}, key = 90
Output: -1
Klasik olarak en ilkel çözüm, tüm diziyi boydan boya aramaktır. O(n)
karmaşıklığa sahiptir.
Bu çözümde ise sıralı diziler üzerinde uygulanan algoritmalardan olan binary search
algoritmasının biraz daha modifiye edilmiş halini kullanacağız.
Fikir olarak şuna dayanmaktadır; elimizdeki değeri ortandaki üç eleman ile karşılaştıracağız. Geri mantık binary search
algoritması gibidir.
Çözüm aşağıdadır.
def mod_binary_search(arr, l, r, x):
'''Modifiye edilmiş binary search'''
if r >= l:
mid = l + (r - l) // 2
# orta 3 eleman ile karşılaştırma
if arr[mid] == x:
return mid
if mid > l and arr[mid - 1] == x:
return mid - 1
if mid < r and arr[mid + 1]:
return mid + 1
# Eğer eleman ortancadan küçükse, sola doğru kaydır
if arr[mid] > x:
return mod_binary_search(arr, l, mid - 2, x)
# Aksi halde sağa doğru kaydır
return mod_binary_search(arr, mid + 2, r, x)
# Bulunamadı
return -1
if __name__ == '__main__':
arr = [3, 2, 10, 4, 40]
target = 4
result = mod_binary_search(arr, 0, len(arr) - 1, target)
if result != -1:
print(result)
else:
print("bulunamadi")
Algoritmanın karmaşıklığı O(logn)
olur.
Comments
comments powered by Disqus