Linear Search Iterative

algorithm.md

###Linear search - Traverse each element to check for a match

Linear search can be implemented upon almost any types of iterable, whether it be array, list, linked-list, etc.

LINEAR_SEARCH(ITERABLE L, element_to_search):
	FOR i = L.FIRST TO L.LAST:
		IF L[i] == element_to_search:
			RETURN i
		END IF
	END FOR
	RETURN FALSE
END LINEAR_SEARCH

Start iterating over the elements.
If a match is found at index i, return this index to indicate that the element exists at index i.
If the loop reaches the last element, we can conclude that no matching elements have been encountered. In that case return false.

Since every elements are visited individually, complexity can be coined as O(n).
However if the element is located at starting index, it would be our best case scenario resulting in O(1). The worst case is when the element doesn't even exist or if it does, it exists at the last index. The loop will be iterating over the complete list making it an O(n).

linear-search.c

/*
	LINEAR SEARCH
	0 based indexing
	array as iterable
	iterative method
	** for TURBO C, remove // from commented statements
*/

#include<stdio.h>
#include<malloc.h>
//#include<conio.h>

/* Since there's no boolean type in c, and -1 will never appear as an index */
#define FALSE -1

int LINEAR_SEARCH(int *arr, int arr_length, int element_to_search){
	int i;
	
	for(i = 0; i < arr_length; i++){
		if(arr[i] == element_to_search){
			return i;
		}
	}
	return FALSE;
}

int main(){
	int index, element_to_search, arr_length = 10;
	int arr[] = { 132, 332, 76, 790, 1, 7, 70, 9, 29, 6 };

	//clrscr();

	printf("\nEnter element to search: "); scanf("%d", &element_to_search);
	
	index = LINEAR_SEARCH(arr, arr_length, element_to_search);

	if(index != -1){
		printf("The search for %d succeeded. First occurence at index %d i.e. position %d.", element_to_search, index, index + 1);
	}else{
		printf("The search for %d failed. NOT FOUND.", element_to_search);
	}

	printf("\n");
	//getch();
	return 0;
}

LinearSearch.java

/*
	LINEAR SEARCH
	0 based indexing
	array as iterable
	iterative method
	Save File as LinearSearch.java
*/

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class LinearSearch{

	static int LINEAR_SEARCH(int[] arr, int element_to_search){
		/* Why static? Since we are calling from main, which itself is static */
		
		for(int i = 0; i < arr.length; i++){
			if(arr[i] == element_to_search){
				return i;
			}
		}
		return -1;
	}	
 
	public static void main(String s[]) throws NumberFormatException, IOException{
		BufferedReader ip = new BufferedReader(new InputStreamReader(System.in));
		int index, element_to_search;
		int arr[] = { 132, 332, 76, 790, 1, 7, 70, 9, 29, 6 };

		System.out.print("\nEnter element to search: "); element_to_search = Integer.parseInt(ip.readLine());
		
		index = LINEAR_SEARCH(arr, element_to_search);

		if(index != -1){
			System.out.print("The search for " + element_to_search + " succeeded. First occurence at index " + index + " i.e. position " + (index + 1) + ".");
		}else{
			System.out.print("The search for " + element_to_search + " failed. NOT FOUND.");
		}

		System.out.print("\n");
	}
}