Two-Way Linear Search Algorithm in C++
Two-Way Linear Search Algorithm in C++
Although the search is carried out from both ends towards the center of the array, the two-way linear search algorithm is based on the linear search concept. This article will cover the Algorithm's foundations, benefits, application, and other details. When using a two-way linear search strategy, we simultaneously begin our search at both ends of the array and work our way toward the center until we locate the desired element.
In two-way linear search algorithm, it contains two pointers, one pointing at the beginning and the other at the conclusion, and the elements at the beginning and end are compared to the target element. We know we have located the target element if any of them equals the target. If not, we repeat the comparison of the related elements by moving the start to the next index and the end to the previous index. When the target element is found or when the start and end cross over (start > end), The Way Linear Search comes to an end.
A simple search method called a linear search algorithm, sometimes referred to as a sequential search algorithm, iteratively searches a list or array for a specific element. Until a match is found or the list's end is reached, the linear search method iterates through each element in the list or array and compares it with the target element. When the list reaches its end, it indicates that the target element is missing from the array.
Algorithm for Linear Search:
The following steps make up the linear search algorithm:
- Get going: Start with the first element in the group of items.
- Evaluate: Make a comparison between the intended and current elements.
- Discovered: If the current element and the desired element are equal, return true or the current element's index.
- Relocate: If not, proceed to the following item in the collection.
- Continue: Continue from steps 2-4 until the collection is complete.
- Not located: If the required element is not found in the array by the time the collection ends, return that information.
Algorithm for Two-Way Linear Search:
Step-by-step instructions for the Two-Way Linear Search algorithm are provided below.
- Set the search indices to start=0 and end=N-1, where N is the array's size.
- While the elements at index start and end do not equal the search element, the start should be increased by 1, and the finish should be decreased by 1.
- The loop ends when it hits the middle of the array; therefore, keep looping until start = end.
- Return the element's index if it can be located; if not, return -1.
Linear Search Applications:
Unsorted Array: The most popular method for locating any element in a collection when dealing with unsorted arrays or lists is linear search.
Tiny sets of data: When dealing with small data sets, linear search is preferable to binary search.
Looking through Linked Lists: Linear search is frequently utilized in linked list implementation to locate elements within a list. Up until the requested element is located, each node is examined in turn.
Easy to Use Implementation: Comparing Linear Search to Binary or Ternary Search, the former is far simpler to comprehend and apply.
Using linear search is possible even if the array isn't sorted. Any type of data array can use it, and it needs no more RAM to function. This technique works well for tiny datasets. Because linear search has an O(N) time complexity, it is slow when dealing with huge datasets, making it not appropriate for big arrays.
Implementing the Algorithm for Two-Way Linear Search:
The Two-Way Linear Search Algorithm implementation is shown below:
#include <iostream> using namespace std; // Function to perform Two Way Linear Search int search(int arr[], int target, int size) { // Initialize the starting and ending pointers int start = 0, end = size - 1; // Iterate till start and end cross each other while (start <= end) { // If the start element is equal to target, return // start as the index of target element if (arr[start] == target) { return start; } // If the ending element is equal to target, return // end as the index of target element if (arr[end] == target) { return end; } start++; end--; } return -1; } // Main code int main() { // Sample Input int arr[] = { 3, 9, 12, 16, 20 }; int target = 12; int size = sizeof(arr) / sizeof(arr[0]); int pos = search(arr, target, size); if (pos == -1) { cout << "Element not in array" << endl; } else { cout << "Element is present at index " << pos << endl; } return 0; }
Output:
Element is present at index 2