Algorithms/Searching.cpp at master · nikipr1999/Algorithms · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
#include<iostream>
using namespace std;

 // to search in an array by:
 // 1. Unordered linear search
 // 2. Ordered linear search
 // 3. Binary search
 // 4. Interpolation search

  /* Other methods of searching are:
    Binary search trees
    Symbol Tables and Hashing
    String searching algorithms : Tries, Ternary Search , Suffix Trees
  */

  int UnorderedLinearSearch(int A[],int n, int data)
  {
      for(int i=0;i<n;i++)
      {
          if(A[i]==data)
         return i;
      }
      return -1;
  }

  int OrderedLinearSearch(int A[],int n, int data)
  {
      for(int i=0;i<n;i++)
      {
          if(A[i]==data)
                return i;

         else if(A[i]>data)
                 return -1;
      }
      return -1;
  }

  // Iterative Binary Search Algorithm
  int BinarySearchIterative(int A[],int n, int data)
  {
        int low=0, high=n-1,mid;
        while(low<high)
        {
            mid=(high+low)/2;
            if(A[mid]==data)
                return mid;

            else if(A[mid]<data)
                low=mid+1;

            else
                high=mid-1;
        }

      return -1;
  }

  //Recursive Binary Search Algorithm
  int BinarySearchRecursive(int A[],int low,int high, int data)
  {
        int mid;
        mid=(high+low)/2;

            if(low>high)
                return -1;
            if(A[mid]==data)
                return mid;

            else if(A[mid]<data)
               return BinarySearchRecursive(A,mid+1,high,data);

            else
              return BinarySearchRecursive(A,low,mid-1,data);

      return -1;
  }

  // Interpolation Search

  /* Interpolation is a process of constructing new data points within the range
     of a discrete set of known data points
     It is often required to interpolate (i.e. estimate) the value of that function
     for an intermediate value of the independent variable.
  */

  int InterpolationSearch(int A[],int n, int data)
  {
        int low=0, high=n-1,mid;
        while(low<high)
        {

            mid=low + (data-A[low])*(high-low)/(A[high]-A[low]);   //  The pivot is selected

            if(A[mid]==data)
                return mid;

            else if(A[mid]<data)
                low=mid+1;

            else
                high=mid-1;
        }

      return -1;
  }

  int main()
  {
      int A[10]={1,2,43,67,4,5,132,2,3,373};
      int B[10]={10,20,25,30,33,45,56,57,58,90};

       cout<< "\n\tUnordered Linear Search : "<<UnorderedLinearSearch(A,10,3);

       cout<< "\n\tOrdered Linear Search : "<<OrderedLinearSearch(B,10,30);

       cout<< "\n\tBinary Search Iterative : "<<BinarySearchIterative(B,10,45);

       cout<< "\n\tBinary Search Recursive : "<<BinarySearchRecursive(B,0,9,56);

       cout<< "\n\tInterpolation Search : "<<InterpolationSearch(B,10,58);

      return 0;
  }