Searching Algorithms on Array


What is Algorithm?

An algorithm is considered as a step by step procedure to perform certain specific task. It is a set of instructions to perform a predefined function. An algorithm is not a code or a program rather an algorithm is only the instructions to solve a particular problem. Through an algorithm a program is implemented. An algorithm can be expressed as a pseudocode or it can be expressed in pictorial form. The pictorial form of an algorithm is known as flowchart.

An algorithm will be more efficient when it will take less time and memory space to perform certain specific task. We can measure the performance of an algorithm on the basis of two aspects that is time and space. The algorithm should take less time to solve the problem and should also consume less memory space.

An element in an array can be searched by using two ways that are linear search and binary search.


Linear Search:

Linear searching is considered to be the simplest search. It searches the element from the array in a sequence. The element to be found is compared with all elements in the array and if the element is found in the array it returns the value index else it returns -1.


Example with Implementation:

Suppose we have the following array of 9 elements and want to search 10 from the array by using linear search. The searching will be done in a sequence.

4 2 3 8 10 12 11 7 5

The following will be the implementation of linear search to find 10 from the above array.

CODE:

int findingIndex (array, n)

 {

   for(int x = 0; x < array. length; ++ x)

     {

       if (array [x] == n)

         {

           return x;

         }

     }

   return -1;

 }

The above method that is findingIndex () can be called by using the following statement.

findingIndex([ 4 , 2 , 3 , 8 , 10, 12, 11, 7, 5 ] , 10) ;

In the above code, the array of elements and the number to be found is passed to the function findingIndex (). We used a ‘for loop’ to find the element n. If the element is found the index of the array will be returned else -1 will be returned. This is the basic concept of linear searching.

It should be noted that linear search is applied on unsorted list of elements.


Binary Search:

We apply the binary searching on sorted list of elements and is used when there are a large number of elements in the array. As the array or list of elements is sorted therefore to search an item using binary search we will compare that item or element with the element that is in the middle position of the array.

If the element is matched we will return the element. If the element to be found is not matched with middle position element, then either the element will be smaller than or larger than middle position element. If the element is smaller than middle position element then we will search for it in the lower half of the array. And if it is greater, then we will search for it in the upper half of the array. This process is repeated until the array is sorted.


Example with Implementation:

Suppose we have the following array of 9 elements and want to search 10 from the array by using binary search.

2 3 4 6 8 9 10 11 12

The above array is sorted in ascending order; hence we can apply binary sorting. It should be noted here that binary sorting can only be applied to sorted list of elements. Searching will be started from middle position.

If middle position element is the one that we are finding then further searching will be stopped and index will be returned. If value to be found is less than middle position element then we will move to the left of the array and if the value to be found is greater than the middle position then we will move to right side of the array. This process will be repeated until we find our element.

The following will be the implementation of binary search to find 10 from the above array:

CODE:

int findingIndex (array, n)

{

  return binarySearching (array, n, 0, array. length – 1);

};

int binarySearching (array, n, s, e)

{

  if (s > e)

{

return -1;

}

  int middleposition = Math. floor ((start + end) / 2);

  int element = array [middleposition];

  if (element > n) { return binarySearching (array, n, s, middleposition-1); }

  if (element < n) { return binarySearching (array, n, middleposition+1, e); }

  return middleposition;

}

The above function that is int findingIndex () can be called by using the following statement and passing an array of integers with a number to be found.

findingIndex ([2, 3, 4, 6, 8, 9, 10, 11, 12], 10);