int linearSearch(int n, int num, vector<int> &arr)
{
// Write your code here.
int flag = -1;
for(int i=0;i<n;i++)
{
if(arr[i] == num)
{
flag = i;
break;
}
}
return flag;
}
Problem
Submissions
Hints & solutions
Discuss
Linear Search
Easy
0/40
Average time to solve is 5m
Contributed by
179 upvotes
Problem statement
You are given an array ‘arr’ containing ‘n’ integers. You are also given an integer ‘num’, and your task is to find whether ‘num’ is present in the array or not.
If ‘num’ is present in the array, return the 0-based index of the first occurrence of ‘num’. Else, return -1.
Input: ‘n’ = 5, ‘num’ = 4
'arr' = [6,7,8,4,1]
Output: 3
Explanation:
4 is present at the 3rd index.
Detailed explanation ( Input/output format, Notes, Images )
Input Format:
The first line contains two integers, ‘n’ and ‘num,’ representing the number of elements in the array and the number to be searched for.
The next line contains ‘n’ space-separated integers representing the elements of the array.
Return an integer, the 0-based index of the first occurrence of ‘NUM’. Else, return -1.
Sample Input 1:
5 4
6 7 8 4 1
Sample Output 1 :
3
Explanation Of Sample Input 1:
4 is present at the 3rd index.
Sample Input 2:
4 2
2 5 6 2
Sample Output 2 :
0
Explanation Of Sample Input 1:
2 is not present in the given array.
Expected time complexity:
The expected time complexity is O(n).
Constraints:
1 <= 'n' <= 10^6
1 <= 'arr'[i] <= 1000
Time Limit: 1 sec
Hint
Hint 1
Brute Force
Approaches (1)
Approach 1
Linear Seach
The solution to the problem lies in traversing the array and checking whether the current element is ‘num’ or not; if we find the ‘num’ for the first time, we will store the index in the ‘ans’ variable and break from the loop.
The steps are as follows:
Function int linearSearch( int ‘n’ , int ‘num’ , [int] ‘arr’ )
- Create an ‘ans’ variable and initialize it with -1.
- For loop ‘idx’ in range 0 to ‘n’-1.
- If ‘arr’[idx] is equal to ‘num’.
- Update ‘ans’ to ‘idx’.
- Break from the for loop.
- If ‘arr’[idx] is equal to ‘num’.
- Return ans.
Time Complexity
O( N ), Where N is the size of the array.
For the worst case, we are iterating all the elements of the array once.
Hence the time complexity is O( N ).
Space Complexity
O(1).
We are not using extra space except for some variables to update the and.
Hence the space complexity is O(1).
Code Solution
(100% EXP penalty)
Linear Search
All tags
Sort by
Interview problems
LINEAR SEARCH IN C++
int linearSearch(int n, int num, vector<int> &arr)
{
for(int i=0;i<n;i++){
if(arr[i]==num){
return i;
}
}
return -1;
// Write your code here.
}
8 views
0 replies
0 upvotes
Interview problems
cpp solution
int linearSearch(int n, int num, vector<int> &arr)
{
// Write your code here.
for(int i=0;i<n;i++)
{
if(arr[i]==num)
{
return i;
}
}
return -1;
}
14 views
0 replies
0 upvotes
Interview problems
Linear Search - C++
int linearSearch(int n, int num, vector<int> &arr)
{
// Write your code here.
int i;
for(i=0;i<arr.size();i++){
if(arr[i]==num){
return i;
}
}
return -1;
}
5 views
0 replies
0 upvotes
Interview problems
c++ solution
int linearSearch(int n, int num, vector<int> &arr)
{
// Write your code here.
int i;
for(i=0;i<arr.size();i++){
if(arr[i]==num){
return i;
}
}
return -1;
}
51 views
0 replies
0 upvotes
Interview problems
LINEAR SEARCH (Best Solutions ) - JAVA
import java.util.*;
public class Solution {
public static int linearSearch(int n, int num, int []arr){
// Write your code here.
for(int i=0; i<arr.length; i++){
if (arr[i] == num) {
return i;
}
}
return -1;
}
}
70 views
0 replies
0 upvotes
Interview problems
Simple C++ solution
int linearSearch(int n, int num, vector<int> &arr) {
// Write your code here.
for(int i=0; i<n; i++){
if (arr[i] == num) {
return i;
}
else {
continue;
}
}
return -1;
} 49 views
0 replies
0 upvotes
Interview problems
Best java solution for Linear search
//Java Most Accurate Solution of Linear Search
import java.util.*;
public class Solution {
public static int linearSearch(int n, int num, int []arr){
// Write your code here.
for(int i=0;i<n;i++){
if(arr[i]==num){
return i;//return index
}
}
return -1;//if num not there in Array return -1
}
}
//please vote if this helpful
44 views
1 reply
0 upvotes
Interview problems
Linear Search
int linearSearch(int n, int num, vector<int> &arr)
{
int i;
for(i=0;i<n;i++)
{
if(arr[i]==num)
return i;
}
return -1;
}
38 views
0 replies
0 upvotes
Interview problems
Best cpp Solution
int linearSearch(int n, int num, vector<int> &arr)
{
for(int i = 0 ; i < n ; i++){
if(arr[i]==num){
return i;
}
}
return -1;
}
23 views
0 replies
0 upvotes
1
2
3
4
C++ (g++ 5.4)
Console