Doğrusal Arama ve İkili Arama

Python'da Veri Yapıları ve Algoritmalar

Miriam Antona

Software engineer

Arama algoritmaları

Arama, temel bir işlemdir
- Birden çok yol
Bir koleksiyonda öğe arayan algoritmalar:
- Doğrusal arama
- İkili arama

Doğrusal arama

Her öğe üzerinde döngü kurma

Sırasız sayılardan oluşan bir listenin şematik gösterimi.

Öğre bulundu
- algoritma durur
- sonuç döndürülür
Öğre bulunamadı
- algoritma devam eder

Doğrusal arama

def linear_search(unordered_list, search_value):

  for index in range(len(unordered_list)):

    if unordered_list[index] == search_value:

      return True

  return False

print(linear_search([15,2,21,3,12,7,8], 8))

True

print(linear_search([15,2,21,3,12,7,8], 800))

False

Doğrusal arama - karmaşıklık

Karmaşıklık: $O(n)$

İkili arama

Yalnızca sıralı listelerde geçerlidir

Sıralı sayılar içeren bir listenin şematik gösterimi.

15 ???

İkili arama

Yalnızca sıralı listelerde geçerlidir

Sıralı sayılar içeren bir listenin şematik gösterimi. Listenin ilk konumunu işaret eden first adlı bir değişken var.

15 ???

def binary_search(ordered_list, search_value):
  first = 0

İkili arama

Yalnızca sıralı listelerde geçerlidir

Sıralı sayılar içeren bir listenin şematik gösterimi. Listenin ilk konumunu işaret eden first adlı bir değişken ve son konumu işaret eden last adlı başka bir değişken var.

15 ???

def binary_search(ordered_list, search_value):
  first = 0
  last = len(ordered_list) - 1


  while first <= last:

İkili arama

Yalnızca sıralı listelerde geçerlidir

Sıralı sayılar içeren bir listenin şematik gösterimi. Listenin ilk konumunu işaret eden first, son konumu işaret eden last ve orta konumu işaret eden middle adlı değişkenler var.

15 ???

def binary_search(ordered_list, search_value):
  first = 0
  last = len(ordered_list) - 1

  while first <= last:
    middle = (first + last)//2

İkili arama

Yalnızca sıralı listelerde geçerlidir

Sıralı sayılar içeren bir listenin şematik gösterimi. Listenin ilk konumunu işaret eden first, son konumu işaret eden last ve orta konumu işaret eden middle adlı değişkenler var. Ortadaki sayı 12 ve sarı renkte.

15 ???
search_value değerini listenin ortasındaki öğe ile karşılaştırın

def binary_search(ordered_list, search_value):
  first = 0
  last = len(ordered_list) - 1

  while first <= last:
    middle = (first + last)//2

    if search_value == ordered_list[middle]:

      return True

    elif search_value < ordered_list[middle]:

İkili arama

Yalnızca sıralı listelerde geçerlidir

Sıralı sayılar içeren bir listenin şematik gösterimi. Listenin ilk konumunu işaret eden first, orta eksi bir konumunu işaret eden last ve orta konumu işaret eden middle adlı değişkenler var. İlk ve orta konumlar arasındaki öğeler yeşil renkte.

15 ???
search_value değerini listenin ortasındaki öğe ile karşılaştırın

def binary_search(ordered_list, search_value):
  first = 0
  last = len(ordered_list) - 1

  while first <= last:
    middle = (first + last)//2
    if search_value == ordered_list[middle]:
      return True
    elif search_value < ordered_list[middle]:
      last = middle - 1

İkili arama

Yalnızca sıralı listelerde geçerlidir

15 ???
search_value değerini listenin ortasındaki öğe ile karşılaştırın

def binary_search(ordered_list, search_value):
  first = 0
  last = len(ordered_list) - 1

  while first <= last:
    middle = (first + last)//2
    if search_value == ordered_list[middle]:
      return True
    elif search_value < ordered_list[middle]:
      last = middle - 1
    else:

İkili arama

Yalnızca sıralı listelerde geçerlidir

Sıralı sayılar içeren bir listenin şematik gösterimi. Listenin ilk konumunu orta artı bire işaret eden first, son konumu işaret eden last ve orta konumu işaret eden middle adlı değişkenler var. İlk ve orta konumlar arasındaki öğeler yeşil renkte.

15 ???
search_value değerini listenin ortasındaki öğe ile karşılaştırın

def binary_search(ordered_list, search_value):
  first = 0
  last = len(ordered_list) - 1

  while first <= last:
    middle = (first + last)//2
    if search_value == ordered_list[middle]:
      return True
    elif search_value < ordered_list[middle]:
      last = middle - 1
    else:
      first = middle + 1

İkili arama

Yalnızca sıralı listelerde geçerlidir

Sıralı sayılar içeren bir listenin şematik gösterimi. Middle işaretçisi hareket etti ve first ile last arasında kalan öğeyi işaret ediyor. İlk ve orta konumlar arasındaki öğeler yeşil renkte.

15 ???
search_value değerini listenin ortasındaki öğe ile karşılaştırın

def binary_search(ordered_list, search_value):
  first = 0
  last = len(ordered_list) - 1

  while first <= last:
    middle = (first + last)//2
    if search_value == ordered_list[middle]:
      return True
    elif search_value < ordered_list[middle]:
      last = middle - 1
    else:
      first = middle + 1

İkili arama

Yalnızca sıralı listelerde geçerlidir

15 ???
search_value değerini listenin ortasındaki öğe ile karşılaştırın

def binary_search(ordered_list, search_value):
  first = 0
  last = len(ordered_list) - 1

  while first <= last:
    middle = (first + last)//2
    if search_value == ordered_list[middle]:
      return True
    elif search_value < ordered_list[middle]:
      last = middle - 1
    else:
      first = middle + 1

İkili arama

Yalnızca sıralı listelerde geçerlidir

Sıralı sayılar içeren bir listenin şematik gösterimi. Last işaretçisi taşındı ve first ile aynı sayıyı işaret ediyor.

15 ???
search_value değerini listenin ortasındaki öğe ile karşılaştırın

def binary_search(ordered_list, search_value):
  first = 0
  last = len(ordered_list) - 1

  while first <= last:
    middle = (first + last)//2
    if search_value == ordered_list[middle]:
      return True
    elif search_value < ordered_list[middle]:
      last = middle - 1
    else:
      first = middle + 1

İkili arama

Yalnızca sıralı listelerde geçerlidir

Sıralı sayılar içeren bir listenin şematik gösterimi. Middle işaretçisi taşındı ve first ile last ile aynı sayıyı işaret ediyor.

15 ???
search_value değerini listenin ortasındaki öğe ile karşılaştırın

def binary_search(ordered_list, search_value):
  first = 0
  last = len(ordered_list) - 1

  while first <= last:
    middle = (first + last)//2
    if search_value == ordered_list[middle]:
      return True
    elif search_value < ordered_list[middle]:
      last = middle - 1
    else:
      first = middle + 1

İkili arama

Yalnızca sıralı listelerde geçerlidir

Sıralı sayılar içeren bir listenin şematik gösterimi. First, last ve middle işaretçileri aynı sayı olan 15’i işaret ediyor; bu sayı 15 ile karşılaştırılacak.

15 ???
search_value değerini listenin ortasındaki öğe ile karşılaştırın

def binary_search(ordered_list, search_value):
  first = 0
  last = len(ordered_list) - 1

  while first <= last:
    middle = (first + last)//2
    if search_value == ordered_list[middle]:
      return True
    elif search_value < ordered_list[middle]:
      last = middle - 1
    else:
      first = middle + 1

İkili arama

Yalnızca sıralı listelerde geçerlidir

Sıralı sayılar içeren bir listenin şematik gösterimi. 15 sayısı daire içine alınmış.

15 ???
search_value değerini listenin ortasındaki öğe ile karşılaştırın

def binary_search(ordered_list, search_value):
  first = 0
  last = len(ordered_list) - 1

  while first <= last:
    middle = (first + last)//2
    if search_value == ordered_list[middle]:
      return True
    elif search_value < ordered_list[middle]:
      last = middle - 1
    else:
      first = middle + 1

  return False

İkili arama - karmaşıklık

Karmaşıklık: $O(\log{}n)$

Doğrusal arama ve ikili aramanın grafiksel gösterimi.

Vamos praticar!

Python'da Veri Yapıları ve Algoritmalar