day28

Day 28 - Search and Sort Algorithms Part A: the Linear Search

It's almost a month sincec we starated this initiative and we did questions on Strings, Arrays, Recursion and Misc. Also, in some questions, we tried to solve the question in best possible runtime, which improved our concepts of time complexity. Now, to make our code more efficient, it's highly essential that we know some frequently used searching and sorting algorithms and apply them in the code accordingly whenever required.

So this week we will be be focusing on various searching and sortinig algorithms. Today's Algorithm -- Linear Search

Question

Write a program to implement linear search, to find the index of a given element in a given array

Example

input: arr = [1, 2, 3, 4, 5], num = 2
output: 1 (index of found element)
input: arr = [1, 2, 3, 4, 5], num = 7
output: undefined

Solution

JavaScript Implementation

functionlinearSearch(arr,n){for(leti=0;i<arr.length;i++)if(arr[i]===n)returni;returnundefined;}console.log(linearSearch([1,2,3,4,5],2));console.log(linearSearch([1,2,3,4,5],7));

Java Implementation

Solution

/** * @date 28/01/19 * @author SPREEHA DUTTA */importjava.util.*;
publicclasslinearSearch1 {
publicstaticvoidmain(String []args)
{
Scannersc=newScanner(System.in);
intn;inti;intp,c=-1;
System.out.println("Enter size and array elements");
n=sc.nextInt();
intarr[]=newint[n];
for(i=0;i<n;i++)
arr[i]=sc.nextInt();
System.out.println("Enter element to be found");
p=sc.nextInt();
for(i=0;i<n;i++)
if(arr[i]==p)
{
c=i;
break;
}
if(c!=-1)
System.out.println(c);
elseSystem.out.println("undefined");
}
}

C++ Implementation

Solution

/** @author : imkaka* @date : 29/1/2019*/
#include<iostream>
#include<vector>usingnamespacestd;intlinearSearch(vector<int> arr, int val){
int size = arr.size();
for(int i = 0; i < size; ++i){
if(arr[i] == val)
return i;
return -1;
}
intmain(){
vector<int> arr = {1, 2, 5, 10, 6, 100};
vector<int> arr2 = {500, 22, 101, 10, 6, 0};
int val = 10;
int val2 = 1;
cout << linearSearch(arr, val) << endl;
cout << linearSearch(arr2, val2) << endl;
return0;
}

C Implementation

Solution

/* * @author : ashwek * @date : 29/01/2019 */#include<stdio.h>#include<stdlib.h>intlinear_search(int*arr, intn, intsearch){
inti;
for(i=0; i<n; i++){
if( arr[i] ==search )
returni;
}
return-1;
}
voidmain(){
int*arr, n, search, i;
printf("Enter size of array = ");
scanf("%d", &n);
arr= (int*)malloc(sizeof(int)*n);
printf("Enter %d elements : ", n);
for(i=0; i<n; i++){
scanf("%d", &arr[i]);
}
printf("Enter a value to search = ");
scanf("%d", &search);
i=linear_search(arr, n, search);
if( i==-1 ){
printf("%d not found in array", search);
}
else{
printf("%d found at %d index", search, i);
}
}