ค้นหาเชิงเส้น

เทคนิคการค้นหาเชิงเส้นเป็นเทคนิคที่ง่ายที่สุด ในเทคนิคนี้ รายการจะถูกค้นหาทีละรายการ ขั้นตอนนี้ใช้ได้กับชุดข้อมูลที่ไม่ได้เรียงลำดับด้วย การค้นหาเชิงเส้นเรียกอีกอย่างว่าการค้นหาตามลำดับ มีชื่อเป็นเส้นตรงเนื่องจากความซับซ้อนของเวลาอยู่ในลำดับของ n O(n)

ความซับซ้อนของเทคนิคการค้นหาเชิงเส้น

• ความซับซ้อนของเวลา: O(n)
• ความซับซ้อนของอวกาศ: O(1)

อินพุตและเอาต์พุต

Input:
A list of data:
20 4 89 75 10 23 45 69
the search key 10
Output:
Item found at location: 4

อัลกอริทึม

linearSearch(array, size, key)

ป้อนข้อมูล - อาร์เรย์ที่จัดเรียง ขนาดของอาร์เรย์และคีย์การค้นหา

ผลลัพธ์ − ตำแหน่งของกุญแจ (หากพบ) มิฉะนั้น ตำแหน่งที่ไม่ถูกต้อง

Begin
   for i := 0 to size -1 do
      if array[i] = key then
         return i
   done
   return invalid location
End

ตัวอย่าง

#include<iostream>
using namespace std;

int linSearch(int array[], int size, int key) {
   for(int i = 0; i<size; i++) {
      if(array[i] == key) //search key in each places of the array
         return i; //location where key is found for the first time
   }
   return -1; //when the key is not in the list
}

int main() {
   int n, searchKey, loc;
   cout << "Enter number of items: ";
   cin >> n;
   int arr[n]; //create an array of size n
   cout << "Enter items: " << endl;

   for(int i = 0; i< n; i++) {
      cin >> arr[i];
   }

   cout << "Enter search key to search in the list: ";
   cin >> searchKey;

   if((loc = linSearch(arr, n, searchKey)) >= 0)
      cout << "Item found at location: " << loc << endl;
   else
      cout << "Item is not found in the list." << endl;
}

ผลลัพธ์

Enter number of items: 8
Enter items:
20 4 89 75 10 23 45 69
Enter search key to search in the list: 10
Item found at location: 4