Linear Search

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 list
if match item == value
return the item's location
end if
end for
end 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 করা হয়েছে ।