Searching:

Search algorithm is the step-by-step procedure used to locate specific data among a collection of data. It is considered a fundamental procedure in computing. In computer science, when searching for data, the difference between a fast application and a slower one often lies in the use of the proper search algorithm.

Search algorithms:

1. Linear Search
2. Binary Search
3. Fibonacci Search

Linear Search:

Linear search is a very simple search algorithm. In this type of search, a sequential search is made over all items one by one. Every item is checked and if a match is found then that particular item is returned, otherwise the search continues till the end of the data collection. #### Pseudocode:

 procedure linear_search (list, value)

   for each item in the list
      if match item == value
         return the item's location
      end if
   end for

end procedure

### Binary Search: Binary search is a fast search algorithm with run-time complexity of Ο(log n). This search algorithm works on the principle of divide and conquer. For this algorithm to work properly, the data collection should be in the sorted form.

Binary search looks for a particular item by comparing the middle most item of the collection. If a match occurs, then the index of item is returned. If the middle item is greater than the item, then the item is searched in the sub-array to the left of the middle item. Otherwise, the item is searched for in the sub-array to the right of the middle item. This process continues on the sub-array as well until the size of the subarray reduces to zero.

Pseudocode:

Procedure binary_search
   A ← sorted array
   n ← size of array
   x ← value to be searched

   Set lowerBound = 1
   Set upperBound = n 

   while x not found
      if upperBound < lowerBound 
         EXIT: x does not exists.
   
      set midPoint = lowerBound + ( upperBound - lowerBound ) / 2
      
      if A[midPoint] < x
         set lowerBound = midPoint + 1
         
      if A[midPoint] > x
         set upperBound = midPoint - 1 

      if A[midPoint] = x 
         EXIT: x found at location midPoint
   end while
   
end procedure

Fibonacci Search:

Fibonacci search is an efficient search algorithm based on divide and conquer principle that can find an element in the given sorted array with the help of Fibonacci series in O(log N) time complexity. This is based on Fibonacci series which is an infinite sequence of numbers denoting a pattern which is captured by the following equation:

F(n+1)=F(n)+F(n-1)

where F(i) is the ith number of the Fibonacci series where F(0) and F(1) are defined as 0 and 1 respectively.

The first few Fibonacci numbers are:

0,1,1,2,3,5,8,13….

F(0) = 0 F(1) = 1 F(2) = F(1) + F(0) = 1 + 0 = 1 F(3) = F(2) + F(1) = 1 + 1 = 2 F(4) = F(3) + F(2) = 1 + 2 = 3 and so continues the series

Other searches like binary search also work for the similar principle on splitting the search space to a smaller space but what makes Fibonacci search different is that it divides the array in unequal parts and operations involved in this search are addition and subtraction only which means light arithmetic operations takes place and hence reducing the work load of the computing machine.

Pseudocode:

/* Returns index of x if present,  else returns -1 */
int fibonaccianSearch(int arr[], int x, int n)
{
    /* Initialize fibonacci numbers */
    int fbM2 = 0;   // (m-2)'th Fibonacci number
    int fbM1 = 1;   // (m-1)'th Fibonacci number
    int fbM = fbM2 + fbM1;  // m'th Fibonacci
    // Marks the eliminated range from front
    int offset = -1;
    /* fbM is going to store the smallest Fibonacci
       number greater than or equal to n */
    while (fbM < n)
    {
	fbM2 = fbM1;
	fbM1 = fbM;
	fbM  = fbM2 + fbM1;
    }
    /* while there are elements to be inspected. Note that
       we compare arr[fbM2] with x. When fbM becomes 1,
       fbMm2 becomes 0 */
    while (fbM > 1)
    {
	// Check if fbMm2 is a valid location
	int i = min(offset+fbM2, n-1);

	/* If x is greater than the value at index fbMm2,
	   cut the subarray array from offset to i */
	if (arr[i] < x)
	{
	    fbM  = fbM1;
	    fbM1 = fbM2;
	    fbM2 = fbM - fbM1;
	    offset = i;
	}

	/* If x is greater than the value at index fbMm2,
	   cut the subarray after i+1  */
	else if (arr[i] > x)
	{
	    fbM  = fbM2;
	    fbM1 = fbM1 - fbM2;
	    fbM2 = fbM - fbM1;
	}

	/* element found. return index */
	else return i;
    }

    /* comparing the last element with x */
    if(fbM1 && arr[offset+1]==x)
	return offset+1;

    /*element not found. return -1 */
    return -1;