Searching Algorithms: Linear Search

Saturday, June 30, 2018

Searching Algorithms: Linear Search

 
welcome to this post.

Today I am going to talk about Searching Algorithms.
In this tutorial, I will cover 3 Searching Algorithms
  • Linear Search
  • Binary Search
  • Interpolation Search

So Let start with Linear Search

Linear Search:
From the name, you can get an idea. It searches linearly. One by one.
This algorithm starts the search from the beginning and continues until finding the
desired search index.

For example,
Assume an array from 0 to 10. and you are searching for10. so what will happen?

First, it checks
if 10 is equal to 0 => nope, then
if 10 is equal to 1 => nope, then
.................................................
continue this
if 10 is equal to 10 => yes.

Now it's finding the number.

So it starts from the beginning and continues until it's done.

Let's jump into the code
Create a class and it's constructor take the array size.
class DataK(size:int){
}

create two variable,

  • one is an array that holds the data set
  • other is numberOfTry: an int type variable that will give information,
how many tries need to find the value.

val array: Array<Int> = Array(size,{i -> i})
var numberOfTry = 0

Now Just run a for loop from 1 to the given size and put the data into the array.
init {
    for (i in 1 until size){
         array[i-1] = i
     }
}

The complete Class code in GitHub
Note: This class is used in every searching Algorithms.

Now create the main method and initialize the data and give the size 100000.
val data = DataK(100000)

we want to find 9999
val search = 99999

Set the initial number of try to zero
var numberOfTry = 0

And the last declare a new variable, named it to result and this will hold the result.
everything is set, now I am ready for the main action

To search run a for loop from 0 to the data size and compare the index value with our searching number if find the break the loop and at the end increase the number of tries.

That's is the idea.
See code
for (i in 0 until (data.array.size - 1)) {
    val number = data.array[i]
    if (number == search) {
        result = number as Int
        break
    }

    numberOfTry++
}

Now result:
from the linear search if the result is -1 then the value does not exist and that means data is not found.

so, we print the number of tries to see it actually search or not if the result is not -1 then
we find the data.
print number of trials, to see how much try need to find our data

if (result != -1)
    println("Data found on: $numberOfTry")
else
    println("Data not found try: $numberOfTry")

Output:
Data found on: 99998

so, it takes 99998 try to find 99999.

Check the full source code in Github

Note: If you are from java. Check this on Github.

That is all about the Linear search algorithm.

It is a very simple algorithm. It is not widely used.

we will compare all of the searching algorithms after completing all of those.

In the next part, I will discuss Binary search.

Thank you for reading.
If you have any suggestion or any queries use the comment section.

Happy coding

About Author:

I am Shudipto Trafder,
Since 2015, I write android code. I love to implement new ideas. I use java and also kotlin. Now I am learning Flutter. I love to learn new things and also love to share. And that is the main reason to run this blog.


Let's Get Connected: Facebook Twitter Linkedin Github

No comments :

Subscribe to: Post Comments ( Atom )