Linear Search และ Binary Search

โครงสร้างข้อมูลและอัลกอริทึมใน Python

Miriam Antona

Software engineer

อัลกอริทึมการค้นหา

การค้นหา เป็นการดำเนินการที่สำคัญ
- มีหลายวิธี
อัลกอริทึมสำหรับค้นหาองค์ประกอบใน collection:
- Linear search
- Binary search

Linear search

วนลูปผ่านแต่ละองค์ประกอบ

ภาพแสดงโครงสร้างของลิสต์ที่มีตัวเลขไม่เรียงลำดับ

พบองค์ประกอบ
- อัลกอริทึมหยุดทำงาน
- คืนค่าผลลัพธ์
ไม่พบองค์ประกอบ
- อัลกอริทึมทำงานต่อ

Linear search

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

Linear search - ความซับซ้อน

ความซับซ้อน: $O(n)$

Binary search

ใช้ได้เฉพาะกับลิสต์ที่เรียงลำดับแล้ว

ภาพแสดงโครงสร้างของลิสต์ที่มีตัวเลขเรียงลำดับ

15 ???

Binary search

ใช้ได้เฉพาะกับลิสต์ที่เรียงลำดับแล้ว

ภาพแสดงโครงสร้างของลิสต์ที่มีตัวเลขเรียงลำดับ โดยมีตัวแปรชื่อ first ชี้ไปที่ตำแหน่งแรกของลิสต์

15 ???

def binary_search(ordered_list, search_value):
  first = 0

Binary search

ใช้ได้เฉพาะกับลิสต์ที่เรียงลำดับแล้ว

ภาพแสดงโครงสร้างของลิสต์ที่มีตัวเลขเรียงลำดับ โดยมีตัวแปรชื่อ first ชี้ไปที่ตำแหน่งแรก และตัวแปรชื่อ last ชี้ไปที่ตำแหน่งสุดท้าย

15 ???

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


  while first <= last:

Binary search

ใช้ได้เฉพาะกับลิสต์ที่เรียงลำดับแล้ว

ภาพแสดงโครงสร้างของลิสต์ที่มีตัวเลขเรียงลำดับ โดยมีตัวแปร first ชี้ตำแหน่งแรก ตัวแปร last ชี้ตำแหน่งสุดท้าย และตัวแปร middle ชี้ตำแหน่งกลาง

15 ???

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

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

Binary search

ใช้ได้เฉพาะกับลิสต์ที่เรียงลำดับแล้ว

ภาพแสดงโครงสร้างของลิสต์ที่มีตัวเลขเรียงลำดับ โดยมีตัวแปร first ชี้ตำแหน่งแรก ตัวแปร last ชี้ตำแหน่งสุดท้าย และตัวแปร middle ชี้ตำแหน่งกลาง ตัวเลข 12 อยู่ในตำแหน่งกลางและแสดงสีเหลือง

15 ???
เปรียบเทียบ search_value กับองค์ประกอบที่อยู่ตรงกลางของลิสต์

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

Binary search

ใช้ได้เฉพาะกับลิสต์ที่เรียงลำดับแล้ว

ภาพแสดงโครงสร้างของลิสต์ที่มีตัวเลขเรียงลำดับ โดยมีตัวแปร first ชี้ตำแหน่งแรก ตัวแปร last ชี้ตำแหน่งกลางลบหนึ่ง และตัวแปร middle ชี้ตำแหน่งกลาง องค์ประกอบระหว่างตำแหน่ง first ถึง middle แสดงสีเขียว

15 ???
เปรียบเทียบ search_value กับองค์ประกอบที่อยู่ตรงกลางของลิสต์

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

Binary search

ใช้ได้เฉพาะกับลิสต์ที่เรียงลำดับแล้ว

15 ???
เปรียบเทียบ search_value กับองค์ประกอบที่อยู่ตรงกลางของลิสต์

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:

Binary search

ใช้ได้เฉพาะกับลิสต์ที่เรียงลำดับแล้ว

ภาพแสดงโครงสร้างของลิสต์ที่มีตัวเลขเรียงลำดับ โดยมีตัวแปร first ชี้ตำแหน่งกลางบวกหนึ่ง ตัวแปร last ชี้ตำแหน่งสุดท้าย และตัวแปร middle ชี้ตำแหน่งกลาง องค์ประกอบระหว่างตำแหน่ง first ถึง middle แสดงสีเขียว

15 ???
เปรียบเทียบ search_value กับองค์ประกอบที่อยู่ตรงกลางของลิสต์

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

Binary search

ใช้ได้เฉพาะกับลิสต์ที่เรียงลำดับแล้ว

ภาพแสดงโครงสร้างของลิสต์ที่มีตัวเลขเรียงลำดับ โดย pointer ของ middle เลื่อนไปชี้องค์ประกอบที่อยู่ระหว่าง first และ last องค์ประกอบระหว่าง first ถึง middle แสดงสีเขียว

15 ???
เปรียบเทียบ search_value กับองค์ประกอบที่อยู่ตรงกลางของลิสต์

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

Binary search

ใช้ได้เฉพาะกับลิสต์ที่เรียงลำดับแล้ว

15 ???
เปรียบเทียบ search_value กับองค์ประกอบที่อยู่ตรงกลางของลิสต์

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

Binary search

ใช้ได้เฉพาะกับลิสต์ที่เรียงลำดับแล้ว

ภาพแสดงโครงสร้างของลิสต์ที่มีตัวเลขเรียงลำดับ โดย pointer ของ last เลื่อนมาชี้ตัวเลขเดียวกับ first

15 ???
เปรียบเทียบ search_value กับองค์ประกอบที่อยู่ตรงกลางของลิสต์

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

Binary search

ใช้ได้เฉพาะกับลิสต์ที่เรียงลำดับแล้ว

ภาพแสดงโครงสร้างของลิสต์ที่มีตัวเลขเรียงลำดับ โดย pointer ของ middle เลื่อนมาชี้ตัวเลขเดียวกับ first และ last

15 ???
เปรียบเทียบ search_value กับองค์ประกอบที่อยู่ตรงกลางของลิสต์

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

Binary search

ใช้ได้เฉพาะกับลิสต์ที่เรียงลำดับแล้ว

ภาพแสดงโครงสร้างของลิสต์ที่มีตัวเลขเรียงลำดับ โดย pointer ของ first, last และ middle ชี้ที่ตัวเลข 15 ซึ่งกำลังถูกเปรียบเทียบกับเลข 15

15 ???
เปรียบเทียบ search_value กับองค์ประกอบที่อยู่ตรงกลางของลิสต์

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

Binary search

ใช้ได้เฉพาะกับลิสต์ที่เรียงลำดับแล้ว

ภาพแสดงโครงสร้างของลิสต์ที่มีตัวเลขเรียงลำดับ โดยมีวงกลมล้อมรอบตัวเลข 15

15 ???
เปรียบเทียบ search_value กับองค์ประกอบที่อยู่ตรงกลางของลิสต์

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

Binary search - ความซับซ้อน

ความซับซ้อน: $O(\log{}n)$

ภาพกราฟเปรียบเทียบ linear search และ binary search

มาฝึกกันเถอะ!

โครงสร้างข้อมูลและอัลกอริทึมใน Python