Data Structure and Algorithms Linear Search
Problem :
N সংখ্যক উপাদাদের একটা অ্যারে arr[] দেয়া হবে । এমন একটা সার্চ এর function লিখতে হবে যেখানে x উপাদানটা খুজতে হবে অ্যারে arr[] থেকে ।
# এটা করার আগে Searching Number সম্পর্কে ভালো ধারনা থাকা জরুলি ।
সধারন কিছু উপায়ের মাধ্যমে Linear Search করা যেতে পারে : -
- arr[] এর বামদিক থেকে খুজতে শুরু করতে হবে এবং প্রত্যেকটা উপাদানের সাথে কম্পেয়ার করতে হবে x উপাদানের সাথে Arr[] কে ।
- if x উপাদানটা খুজে পাওয়া যায় arr[] এর মধ্যে তাহলে — return the index.
- if x এর সাথে কোনো উপাদানের মিল না পাওয়া যায় তাহলে — return -1
আমাদেরকে যদি ৩৩ সংখ্যাকে খুজতে হয় তাহলে নিচের উপায়ে আনাল্যসিস করতে হবে ।
Example :
Algorithm
Linear Search ( Array A, Value x)Step 1: Set i to 1
Step 2: if i > n then go to step 7
Step 3: if A[i] = x then go to step 6
Step 4: Set i to i + 1
Step 5: Go to Step 2
Step 6: Print Element x Found at index i and go to step 8
Step 7: Print element not found
Step 8: Exit
Pseudocode
procedure linear_search (list, value)for each item in the listif match item == valuereturn the item's locationend ifend forend procedure
PYTHON CODE:
# Searching an element in a list/array in python
# can be simply done using 'in' operator
# Example:
# if x in arr:
# print arr.index(x)
# If you want to implement Linear Search in python
# Linearly search x in arr[]
# If x is present then return its location
# else return -1
def search(arr, x):
for i in range(len(arr)):
if arr[i] == x:
return i
return -1
JAVA CODE:
classLinearSearch{
// This function returns index of element x in arr[]
static int search(int arr[], int n, int x) {
for (int i = 0; i < n; i++) {
// Return the index of the element if the element
// is found
if (arr[i] == x)
return i;
}// return -1 if the element is not found
return -1;
}
}
Time Complexity:
Linear Search এর Time complexity O(N) কারন প্রত্যেক উপাদানকে অ্যারের মধ্যে compared করা হয়েছে ।