Pencarian Linear dan Biner

Struktur Data dan Algoritma di Python

Miriam Antona

Software engineer

Algoritma pencarian

Pencarian adalah operasi penting
- Ada beberapa cara
Algoritma untuk mencari elemen dalam koleksi:
- Pencarian linear
- Pencarian biner

Pencarian linear

Melakukan loop pada tiap elemen

Representasi skematis daftar angka tidak terurut.

Elemen ditemukan
- algoritma berhenti
- mengembalikan hasil
Elemen tidak ditemukan
- algoritma lanjut

Pencarian linear

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

Pencarian linear - kompleksitas

Kompleksitas: $O(n)$

Pencarian biner

Hanya untuk daftar terurut

Representasi skematis daftar berisi angka terurut.

15 ???

Pencarian biner

Hanya untuk daftar terurut

Representasi skematis daftar berisi angka terurut. Ada variabel bernama first yang menunjuk ke posisi pertama daftar.

15 ???

def binary_search(ordered_list, search_value):
  first = 0

Pencarian biner

Hanya untuk daftar terurut

Representasi skematis daftar berisi angka terurut. Ada variabel bernama first yang menunjuk ke posisi pertama daftar dan variabel last yang menunjuk ke posisi terakhir.

15 ???

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


  while first <= last:

Pencarian biner

Hanya untuk daftar terurut

Representasi skematis daftar berisi angka terurut. Ada variabel bernama first yang menunjuk ke posisi pertama daftar, variabel last yang menunjuk ke posisi terakhir, dan variabel middle yang menunjuk ke posisi tengah.

15 ???

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

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

Pencarian biner

Hanya untuk daftar terurut

15 ???
Bandingkan search_value dengan item di tengah daftar

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]:

Pencarian biner

Hanya untuk daftar terurut

Representasi skematis daftar berisi angka terurut. Ada variabel bernama first yang menunjuk ke posisi pertama daftar, variabel last yang menunjuk ke posisi tengah dikurangi satu, dan variabel middle yang menunjuk ke posisi tengah. Elemen antara posisi first dan middle berwarna hijau.

15 ???
Bandingkan search_value dengan item di tengah daftar

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

Pencarian biner

Hanya untuk daftar terurut

15 ???
Bandingkan search_value dengan item di tengah daftar

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:

Pencarian biner

Hanya untuk daftar terurut

Representasi skematis daftar berisi angka terurut. Ada variabel bernama first yang menunjuk ke posisi tengah ditambah satu, variabel last yang menunjuk ke posisi terakhir, dan variabel middle yang menunjuk ke posisi tengah. Elemen antara posisi first dan middle berwarna hijau.

15 ???
Bandingkan search_value dengan item di tengah daftar

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

Pencarian biner

Hanya untuk daftar terurut

Representasi skematis daftar berisi angka terurut. Pointer middle telah berpindah dan menunjuk ke elemen di antara first dan last. Elemen antara posisi first dan middle berwarna hijau.

15 ???
Bandingkan search_value dengan item di tengah daftar

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

Pencarian biner

Hanya untuk daftar terurut

Representasi skematis daftar berisi angka terurut. Pointer middle telah berpindah dan menunjuk ke elemen di antara first dan last. Elemen antara posisi first dan middle berwarna hijau. Elemen yang ditunjuk middle, 17, akan dibandingkan dengan angka 15.

15 ???
Bandingkan search_value dengan item di tengah daftar

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

Pencarian biner

Hanya untuk daftar terurut

Representasi skematis daftar berisi angka terurut. Pointer last telah dipindah dan menunjuk ke angka yang sama dengan pointer first.

15 ???
Bandingkan search_value dengan item di tengah daftar

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

Pencarian biner

Hanya untuk daftar terurut

Representasi skematis daftar berisi angka terurut. Pointer middle telah dipindah dan menunjuk ke angka yang sama dengan pointer first dan last.

15 ???
Bandingkan search_value dengan item di tengah daftar

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

Pencarian biner

Hanya untuk daftar terurut

Representasi skematis daftar berisi angka terurut. Pointer first, last, dan middle menunjuk ke angka yang sama, 15, yang akan dibandingkan dengan angka 15.

15 ???
Bandingkan search_value dengan item di tengah daftar

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

Pencarian biner

Hanya untuk daftar terurut

Representasi skematis daftar berisi angka terurut. Angka 15 dilingkari.

15 ???
Bandingkan search_value dengan item di tengah daftar

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

Pencarian biner - kompleksitas

Kompleksitas: $O(\log{}n)$

Representasi grafis pencarian linear dan biner.

Ayo berlatih!

Struktur Data dan Algoritma di Python