Skip to main content

Search

การ Search คืออะไร ?​

Search Algorithm หรือ Algorithm การค้นหา คือขั้นตอนวิธีที่ใช้ในการค้นหาข้อมูลหรือค่าที่ต้องการจากชุดข้อมูลหรือโครงสร้างข้อมูลต่างๆ เช่น Array, Linked List เป็นต้น โดยมีวัตถุประสงค์เพื่อหาตำแหน่งหรือ index ของข้อมูลที่ต้องการออกมาได้

โดยปกติประเภทของ Search Algorithm ก็จะมีดังนี้

  1. Linear Search เป็น algorithm การค้นหาแบบง่ายที่สุด โดยจะค้นหาข้อมูลทีละตัวเรียงจากต้นจนสุดท้ายของชุดข้อมูล จนกว่าจะพบข้อมูลที่ต้องการ เหมาะสำหรับข้อมูลที่ไม่ได้จัดเรียงลำดับ
  2. Binary Search ใช้สำหรับข้อมูลที่จัดเรียงลำดับแล้ว โดยจะแบ่งครึ่งข้อมูลออกเป็น 2 ส่วนแล้วเปรียบเทียบกับค่าที่ต้องการค้นหา หากค่ายังไม่ตรงก็จะทำซ้ำกับส่วนที่เหลือจนครบทุกข้อมูล ด้วยไอเดียการแบ่งส่วนนี้ทำให้มีประสิทธิภาพสูงกว่า Linear Search
  3. Jump Search เป็นการปรับปรุงจาก Linear Search โดยจะกระโดดข้ามข้อมูลบางส่วนแทนการค้นหาทีละตัว เหมาะสำหรับข้อมูลขนาดใหญ่ที่จัดเรียงลำดับแล้ว
  4. Depth-First Search (DFS) and Breadth-First Search (BFS) ใช้สำหรับการค้นหาใน Tree หรือ Graph ว่าข้อมูลอยู่ตรงตำแหน่งไหนของ Tree หรือ Graph ได้ (จากที่เราเรียนไปในบทก่อนหน้า)

การประเมินประสิทธิภาพของ Search algorithms โดยปกติ จะพิจารณาจากความซับซ้อนของ time complexity และ space complexity (เดี๋ยวเราจะมีอธิบายในหัวข้อถัดไป) เพื่อช่วยให้ตัดสินใจเลือกใช้ Algorithm ที่เหมาะสมกับสถานการณ์ต่างๆได้

เราจะเจาะจงไปที่ 2 ประเภทก่อน คือ Linear Search และ Binary Search (จริงๆ สำหรับ data แบบ Tree สามารถใช้ BFS และ DFS ในการค้นหาได้เลย)

Linear search เป็น algorithm การค้นหาแบบง่าย โดยจะไล่ตรวจสอบข้อมูลทีละตัวภายใน list หรือ array จนกว่าจะเจอข้อมูลที่ต้องการ หรือไปถึงปลายสุดของ list โดย หากเจอข้อมูลที่ต้องการ Algorithm จะส่งคืนตำแหน่งของข้อมูลนั้นออกมาได้

หลักการของ Linear Search

  1. เริ่มต้นที่ข้อมูลตัวแรกของ list
  2. เปรียบเทียบข้อมูลที่ต้องการค้นหา กับข้อมูลตัวที่กำลังตรวจสอบอยู่
  3. ถ้า ข้อมูลตรงกัน ส่งคืนตำแหน่งของข้อมูลที่กำลังตรวจสอบอยู่ออกมา
  4. ถ้า ข้อมูลไม่ตรงกัน เลื่อนไปตรวจสอบข้อมูลตัวถัดไป และทำตามขั้นตอนที่ 2 และ 3 ต่อไปเรื่อยๆ
  5. ถ้า ตรวจสอบจนถึงข้อมูลสุดท้ายของ list แต่ปรากฎว่าไม่เจอข้อมูลที่กำลังค้นหาอยู่ ส่งคืนว่าข้อมูลที่ต้องการค้นหาไม่มีอยู่ใน list นี้

แปลไทยเป็นไทยแบบง่ายๆเลย “มันคือ loop ค้นหาแบบปกตินั่นแหละ”

code ตัวอย่างของ Linear Search

#include <iostream>
using namespace std;

// Linear search function
int linearSearch(int arr[], int n, int x) {
  for (int i = 0; i < n; i++) {
    if (arr[i] == x) {
      return i; // Return the index if x is found
    }
  }
  return -1; // Return -1 if x is not found
}

int main() {
  int arr[] = {2, 5, 1, 9, 3};
  int n = sizeof(arr) / sizeof(arr[0]); // Size of the array
  int x = 3;                            // Element to search

  int result = linearSearch(arr, n, x);

  if (result == -1) {
    cout << "Element not found in the array" << endl;
  } else {
    cout << "Element found at index " << result << endl;
  }

  return 0;
}

Binary search เป็น Algorithm การค้นหาที่ทำงานบน list ที่เรียงลำดับ โดยแบ่งช่วงการค้นหาออกเป็นครึ่งหนึ่งและค่อยๆค้นหาช่วงที่แบ่งครึ่งไปเรื่อยๆจนครบทุกข้อมูล นับเป็น Algorithm แบบ divide-and-conquer ที่ช่วยลดความซับซ้อนของเวลาลงได้

หลักการทำงานของ binary search

  1. เริ่มต้นด้วยการกำหนดให้ list ทั้งหมดเป็น search space
  2. หาข้อมูลตรงกลางของ search space ในขณะนั้น
  3. เปรียบเทียบข้อมูลตรงกลางกับข้อมูลที่ต้องการค้นหา
  4. ถ้า ข้อมูลตรงกัน ส่งคืนตำแหน่งของข้อมูลตรงกลาง
  5. ถ้า ข้อมูลที่ต้องการค้นหา น้อยกว่าข้อมูลตรงกลาง ให้ค้นหาต่อในครึ่งล่างของ list
  6. ถ้า ข้อมูลที่ต้องการค้นหา มากกว่าข้อมูลตรงกลาง ให้ค้นหาต่อในครึ่งบนของ list
  7. ทำซ้ำขั้นตอนที่ 2-6 จนกว่าจะเจอข้อมูลที่ต้องการค้นหา หรือพื้นที่ค้นหาว่างเปล่า

อย่างเช่นตัวอย่าง animation นี้ที่เรากำลังตามหา 13 อยู่ ใน array nums [1, 3, 5, 6, 8, 11, 13, 15, 17, 22, 24] ขั้นตอนก็คือ

  1. กำหนด Left กับ right pointers มา Left = 0 (index แรกสุด), Right = 10 (index ท้ายสุด)
  2. ให้ array ทั้งหมดเป็น subarray
  3. คำนวน middle index (index ตรงกลาง) ของ subarray Middle = (Left + Right) / 2 = (0 + 10) / 2 = 5
  4. เทียบกับ element ตรงกลาง (ที่ได้ index มา) ว่า ค่ามากกว่าข้อมูลที่กำลังค้นหาหรือไม่
    1. ค่าของ nums[5] = 11
    2. 11 < 13 = ต้องเลื่อน subarray ไปทางขวา
    3. นำ [13, 15, 17, 22, 24] มาเป็น subarray
    4. update Left = 6 (index เริ่มต้นของ subarray ใหม่ ซึ่งก็คือ Middle + 1)
  5. ค้นหา middle index (index ตรงกลาง) ของ subarray ใหม่ Middle = (Left + Right) / 2 = (6 + 10) / 2 = 8
  6. เทียบกับ element ตรงกลาง (ที่ได้ index มา) ว่า ค่ามากกว่าข้อมูลที่กำลังค้นหาหรือไม่
    1. ค่าของ nums[8] = 17
    2. 17 > 13 = ต้องเลื่อน subarray ไปทางซ้าย
    3. นำ [13, 15] มาเป็น subarray
    4. update Right = 7 (index ท้ายสุดของ subarray ใหม่ ซึ่งก็คือ Middle - 1)
  7. ค้นหา middle index (index ตรงกลาง) ของ subarray ใหม่ Middle = (Left + Right) / 2 = (6 + 7) / 2 = 6
  8. เทียบกับ element ตรงกลาง (ที่ได้ index มา) ว่า ค่ามากกว่าข้อมูลที่กำลังค้นหาหรือไม่
    1. ค่าของ nums[6] = 13
    2. 13 = 13 แปลว่าเจอแล้ว !
    3. คำตอบคือ index = 6 คืนออกมา

binary-search.gif

จำเป็นต้องใช้กับ list ที่เรียงลำดับเท่านั้น เพื่อให้การทำงานของ Binary Search ออกมาถูกต้อง เหตุผลเพราะว่า มันอาศัยคุณสมบัติที่ข้อมูลถูกจัดเรียงไว้ตามลำดับ (น้อยไปมาก หรือ มากไปน้อย) ในการ scope การค้นหาออกมา ลำดับนี้ช่วยให้ Algorithm สามารถตัดส่วนที่เหลือของข้อมูลออกไปได้ครึ่งหนึ่งในแต่ละขั้นตอน ผ่านการเปรียบเทียบข้อมูลที่ต้องการค้นหากับข้อมูลตรงกลาง ในทุกครั้งที่เลื่อนไป เราจะมั่นใจได้ว่า ชุดข้อมูลที่เหลือจะไม่อยู่ใน scope ของการค้นหาแล้วเรียบร้อย (เช่นเคสด้านบนที่ เรากำลังหา 13 เมื่อเราเลื่อนไปครึ่งหนึ่งของทางขวา เราก็จะมั่นใจได้ว่าอีกครึ่งหนึ่งทางซ้ายจะไม่มีทางเจอ 13 แน่นอน เพราะ list ได้ทำการเรียงลำดับไว้แล้วเรียบร้อยนั่นเอง)

และนี่คือ code อย่างง่ายของ binary search เมื่อลองเขียน code ออกมาก็จะมีหน้าตาแบบนี้

#include <iostream>
using namespace std;

// Function to perform bubble sort
void bubbleSort(int arr[], int n) {
  for (int i = 0; i < n - 1; i++) {
    for (int j = 0; j < n - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        // Swap arr[j] and arr[j+1]
        int temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
  }
}

// Function to perform binary search
int binarySearch(int arr[], int n, int target) {
  int left = 0, right = n - 1;
  while (left <= right) {
    int mid = left + (right - left) / 2;
    if (arr[mid] == target)
      return mid; // Target found at index mid
    else if (arr[mid] < target)
      left = mid + 1; // Search in the right half
    else
      right = mid - 1; // Search in the left half
  }
  return -1; // Target not found
}

int main() {
  int arr[] = {1, 3, 22, 5, 13, 6, 8, 11, 15, 17, 24}; // Fixed array
  int n = sizeof(arr) / sizeof(arr[0]);                // Size of the array

  bubbleSort(arr, n); // Sort the array using bubble sort

  cout << "Sorted array: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << endl;

  int target = 13; // Target element to search

  int result = binarySearch(arr, n, target); // Perform binary search

  if (result == -1)
    cout << "Target element not found in the array." << endl;
  else
    cout << "Target element found at index " << result << endl;

  return 0;
}

ผลลัพธ์

Sorted array: 1 3 5 6 8 11 13 15 17 22 24 
Target element found at index 6