Locating the record with the specified key value, or locating some or all
There are primarily two main searching algorithms. They are
as follows:
·
Linear Search
Check each item in a list or array one by one to do a search. Another name
for the linear search is “consecutive search”.
Every component of the array is looked at one by one until the desired value
is discovered. A flag value is returned in the absence of the value being
searched for.
(Flag value Null)
Step 1: Having array list and targeting value.
Step 2: Array execute till size-1 (Number of Element in
Array);
Step 3: During step 2 compare each index value with targeting
value
• If value
match “Value exist” and programs exit
• Else skip and
start comparing other value
Step 4: value does not exist, if and only if step 3 violate.
34 |
456 |
23 |
65 |
2 |
54 |
0 |
1 |
2 |
3 |
4 |
5 |
34 |
456 |
23 |
65 |
2 |
54 |
0 |
1 |
2 |
3 |
4 |
5 |
Now this is a drawback of linear search and a worst case in linear search
when value doesn’t exist or targeting value at in last index. The time com-
plexity is O (n). Let there are 1000 value and targeting value doesn’t exist
the linear search's time complexity is still O (n), where "n" is the list's total
number of values, which in this case is 1000.
34 |
456 |
23 |
65 |
2 |
54 |
0 |
1 |
2 |
3 |
4 |
5 |
Let’s search for the number 2. We start at the beginning and check the
first element
in the array. Is it 2?
34 equal
to “2” NO!
34 |
456 |
23 |
65 |
2 |
54 |
0 |
1 |
2 |
3 |
4 |
5 |
456 equal
to “2” NO!
34 |
456 |
23 |
65 |
2 |
54 |
0 |
1 |
2 |
3 |
4 |
5 |
23 equal
to “2” NO!
34 |
456 |
23 |
65 |
2 |
54 |
0 |
1 |
2 |
3 |
4 |
5 |
65 equal
to “2” NO!
34 |
456 |
23 |
65 |
2 |
54 |
0 |
1 |
2 |
3 |
4 |
5 |
2 equal
to “2” Yes!
34 |
456 |
23 |
65 |
2 |
54 |
0 |
1 |
2 |
3 |
4 |
5 |
We found it!!! Now you understand the idea of linear searching;
We go through each element, in order, until we find the correct value
or we don’t till the very end.
#include<iostream>
using namespace std;
void Linear(int arr[], int num,int x) { int a=0; for (int i=0 ; i<num ; i++) { if(arr[i]==x) { a=1; cout<<"Number Present"<<endl; } else { continue; } } if(a!=1) { cout<<"Number does not exist"<<endl; } }
int main() { int arr[]={6,4,15,98,10,7}; int size=6; Linear(arr,size,67);
}
public class LinearSearch {
public static void main(String[] args) { int a = 0; int[] arr = {6, 4, 15, 98, 10, 7}; int x = 67; int num = arr.length; for (int i = 0; i < num; i++) { if (arr[i] == x) { a = 1; System.out.println("Number Present"); break; } } if (a != 1) { System.out.println("Number does not exist"); } } }
a = 0 arr = [6, 4, 15, 98, 10, 7] x = 67 num = len(arr) for i in range(num): if arr[i] == x: a = 1 print("Number Present") break if a != 1: print("Number does not exist")
The Linear Search algorithm would be impossible in practice if we were
searching through a list consisting of thousands of names, as in a telephone
book. However, if the names are sorted alphabetically, as in telephone
books, then we can use an efficient algorithm called binary search.
0 Comments