TOPIC:LINEAR SEARCH
NAME:RAVAL OM P
ENROLLMENT NUMBER:220280152057
-Linear Search is defined as a sequential search algorithm that starts at one end and
goes through each element of a list until the desired element is found, otherwise the
search continues till the end of the data set.
-How Does Linear Search Algorithm Work?
In Linear Search Algorithm,
• Every element is considered as a potential match for the key and checked for the same.
• If any element is found equal to the key, the search is successful and the
index of that element is returned.
• If no element is found equal to the key, the search yields “No match found”.
Step 1: Start from the first element (index 0) and compare key with each element (arr[i]).
Comparing key with first element arr[0]. SInce not equal, the iterator moves to the next
element as a potential match.\
-Comparing key with next element arr[1]. SInce not equal, the iterator moves to the next
element as a potential match.
Step 2: Now when comparing arr[2] with key, the value matches. So the Linear Search Algorithm will
yield a successful message and return the index of the element when key is found (here 2).
➢ IMPLEMENTATION OF LINEAR SEARCH:
TOPIC: BINARY SEARCH
✗ Binary Search is defined as a searching algorithm used in a sorted
array by repeatedly dividing the search interval in half. The idea of
binary search is to use the information that the array is sorted and
reduce the time complexity to O(log N).
✗ Conditions for when to apply Binary Search in a Data Structure:
● The data structure must be sorted.
● Access to any element of the data structure takes constant time.
✗ ALGORITHM:
In this algorithm,
• Divide the search space into two halves by finding the middle index “mid”.
• Compare the middle element of the search space with the key.
• If the key is found at middle element, the process is terminated.
• If the key is not found at middle element, choose which half will be used as the
next search space.
• If the key is smaller than the middle element, then the left side is used for next search.
• If the key is larger than the middle element, then the right side is used for next search.
• This process is continued until the key is found or the total search space is exhausted.
-
✗ IMPLEMENTATION OF BINARY SEARCH