রৈখিক অনুসন্ধান

রৈখিক অনুসন্ধান কৌশল হল সবচেয়ে সহজ কৌশল৷ এই কৌশলে, আইটেমগুলি একে একে অনুসন্ধান করা হয়। এই পদ্ধতিটি সাজানো না হওয়া ডেটা সেটের জন্যও প্রযোজ্য। রৈখিক অনুসন্ধান অনুক্রমিক অনুসন্ধান হিসাবেও পরিচিত। এটিকে রৈখিক হিসাবে নামকরণ করা হয়েছে কারণ এর সময় জটিলতা 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