Linear Search

Given an array of n elements. We have to write a function to search an item X in the given array Arr[n]

Examples :

Input : arr[] = {10, 20, 80, 30, 60, 50,
110, 100, 130, 170}
x = 110;
Output : 6
Element x is present at index 6

Input : arr[] = {10, 20, 80, 30, 60, 50,
110, 100, 130, 170}
x = 175;
Output : -1
Element x is not present in arr[].

A simple approach is to do a linear search

, i.e  

• Start from the leftmost element of arr[] and one by one compare x with each element of arr[]
• If x matches with an element, return the index.
• If x doesn’t match with any of elements, return -1.

C

// C code to linearly search x in arr[]. If x
// is present then return its location, otherwise
// return -1

#include <stdio.h>

int search(int arr[], int n, int x)
{
	int i;
	for (i = 0; i < n; i++)
		if (arr[i] == x)
			return i;
	return -1;
}

// Driver code
int main(void)
{
	int arr[] = { 2, 3, 4, 10, 40 };
	int x = 10;
	int n = sizeof(arr) / sizeof(arr[0]);

	// Function call
	int result = search(arr, n, x);
	(result == -1)
		? printf("Element is not present in array")
		: printf("Element is present at index %d", result);
	return 0;
}

Python3

# Python3 code to linearly search x in arr[].
# If x is present then return its location,
# otherwise return -1


def search(arr, n, x):

	for i in range(0, n):
		if (arr[i] == x):
			return i
	return -1


# Driver Code
arr = [2, 3, 4, 10, 40]
x = 10
n = len(arr)

# Function call
result = search(arr, n, x)
if(result == -1):
	print("Element is not present in array")
else:
	print("Element is present at index", result)

Output

Element is present at index 3

The time complexity of the above algorithm is O(n). 

Linear search is rarely used practically because other search algorithms such as the binary search algorithm and hash tables allow significantly faster-searching comparison to Linear search.

Improve Linear Search Worst-Case Complexity

1. if element Found at last  O(n) to O(1)
2. if element Not found O(n) to O(n/2)

Below is the implementation:

Python

# Python3 program for linear search
def search(arr, search_Element):
	left = 0
	length = len(arr)
	position = -1
	right = length - 1

	# Run loop from 0 to right
	for left in range(0, right, 1):

		# If search_element is found with
		# left variable
		if (arr[left] == search_Element):
			position = left
			print("Element found in Array at ", position +
				1, " Position with ", left + 1, " Attempt")
			break

		# If search_element is found with
		# right variable
		if (arr[right] == search_Element):
			position = right
			print("Element found in Array at ", position + 1,
				" Position with ", length - right, " Attempt")
			break
		left += 1
		right -= 1

	# If element not found
	if (position == -1):
		print("Not found in Array with ", left, " Attempt")

# Driver code
arr = [1, 2, 3, 4, 5]
search_element = 5

# Function call
search(arr, search_element)

Output

Element found in Array at 5 Position with 1 Attempt

Important Notice

If you’re a college student and have skills in programming languages, Want to earn through blogging? Mail us at geekycomail@gmail.com

For more Programming related blogs Visit Us Geekycodes . Follow us on Instagram.