Introduction to Searching Algorithm

Before jumping right into the computers let's build things up from the first principles and understand some basics.

What is searching?

Searching is the act of looking for something, it is an activity that involves exploring and examining different things in a set to find what you are looking for.

The above-written explanation is a bookish definition.

In layman's terms, searching is just doing some process to get the desired thing out, that you want from a collection of things.

For example, searching for a pair of scissors on your desk.

But how it works?

The initial requirement for searching for your desired object (which is a pair of scissors in this case) is that you should have a decent description of your object just to differentiate it from other objects in the collection (that is other objects on your desk).

To determine that a certain object from the set is your desired object, it should satisfy a condition, the condition is, that the object should match with the desired object's description.

The second most important thing is the Set or Collection you are searching for your object in must be well-defined for example your desk can be a well-defined set).

An example can be searching for a person in a city, but it would be wrong if I just search for a person and don't mention where to search, it can be a house, a city, a nation or the whole world.

Now we have all the necessary things to perform searching,

• Object Description → Pair of Scissors

• Set / Collection of Objects → Items on my desk

Now are we ready for searching?

In my view yes, we are. But you can also think of some more factors.

Now let's start searching for our pair of scissors on our desk:

1. Look at the desk,

2. Look at every object and check whether it is satisfying the condition of being a scissor or not,

3. If any object satisfies that condition, it's our object(scissors).

But computers are dumb, we have to provide them with every instruction, and they will perform exactly as they are instructed. They don't know anything; they just do what we want them to do.

With respect to searching, we would have to provide very specific instruction to computer to make things work.

• Algorithms
  (yet another factor to perform searching)

First of all, we have to provide the set or collection of objects in which we want to search. Next, we must provide the computer with the description of object that we want to find.

For simplicity we will take example of searching a particular number from a set of numbers:

• Object Description → A number, for example 7

• Set / Collection of Objects → An array of numbers, for example [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

Now we have to tell the computer how to search (algorithm), in our case searching among the items on the desk is a very common thing and it doesn't require us to follow instructions (algorithms), it is very intuitive. We look at the things on the desk from a bird's eye view and check whether the objects on the desk match the description of the object that we are looking for. Since the computer is a digital machine, it can't look at things from a bird's eye view, so we have to provide some algorithm to the computer. And algorithms are just set of instruction.

Here we will provide an Algorithm very analogous to what we do to search things:

The computer will examine the object or data one at a time from the set and for every object it checks whether that object satisfies the desired object's description, if it does, here is your object!

The above process or approach is called Linear search.

Pseudo Code

Function LinearSearch(List, Target):
    # List: the collection of items to search through
    # Target: the item you want to find

    For each item in List:
        If this item is equal to Target:
            Return the position of this item
    EndFor

    Return "Not Found"  # Target is not in the list

In next blog we will see implementation of linear search and another searching method called binary search.