C Programming: Searching

Sequencial search

เรียกอีกอย่างว่า linear search
เป็นการไล่หาข้อมูลทีละตัว โดยวนลูป

Example code

#include <stdio.h>

int main() {
  int list[] = { 5, 1, 6, 12, 4, 3, 8, 33, 16, 21 };
  int key = 18;
  int size = sizeof(list) / sizeof(list[0]);
  int count = 0;
  for(int i = 0; i < size; i++) {
    if (list[i] == key) { // compares each element of the array
        printf("found at index %d\n", i + 1);
        count = count + 1;
    }
  }
  if (count == 0) {
    printf("not found\n");
  }
}

Binary search

เป็นการหาข้อมูลทีละครึ่ง
ข้อมูลที่ตั้งต้นต้อง Sorting ก่อน
Time complexity (Big-O) = log2n

Instruction

ให้นำข้อมูลที่ Sorting มาเป็นค่าตั้งต้น โดยกำหนด
1. target = ค่าที่ต้องการ search
2. low = index array ตำแหน่งแรก
3. high = index array ตำแหน่งสุดท้าย
4. mid = index array ตำแหน่งตรงกลาง (low + high) / 2
เปรียบเทียบค่า target กับค่า mid ไปเรื่อยๆ
1. ถ้า target < ค่าของ mid => ปรับ high = mid - 1
2. ถ้า target > ค่าของ mid => ปรับ low = mid + 1
ทำแบบนี้ไปเรื่อยๆ จน low > high จึงหยุดทำงาน

Example code

#include <stdio.h>

int main() {
  int list[] = { 1, 5, 7, 8, 11, 13, 18, 21, 33, 35, 41, 52 };
  int target = 35;
  int size = sizeof(list) / sizeof(list[0]);

  int first, mid, last, res;
  first = 0;
  last = size - 1;
  res = -1;

  while (first <= last) {
    mid = (first + last) / 2;
    
    if (list[mid] == target) {
      res = mid;
      break;
    } else if (target > list[mid]) {
      first = mid + 1;
    } else if (target < list[mid]) {
      last = mid - 1;
    } else {
      first = last + 1; // force end
    }
  }
  printf("index = %d", res);
}

C Programming: Searching

Sequencial search

Binary search

Sequencial search VS binary search

Reference

Pathompat Sungpankhao