search-algorithms/SearchAlgorithm.h at main · ertello/search-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
#ifndef _SEARCH_ALGORITHM_H_
#define _SEARCH_ALGORITHM_H_

#include <iostream>
#include <vector>

template <class T>
class SearchAlgorithm {
  public:
    SearchAlgorithm();
    ~SearchAlgorithm();
    int busquedaSecuencial(std::vector<T> &A, T key, int &compara);
    int busquedaSecuencialVectorOrdenado(std::vector<T> &A, T key, int &compara);
    int busquedaBinaria(std::vector<T> &A, T key, int &compara);
    int busquedaBinariaRecursiva(std::vector<T> &A, int low, int high, T key, int &compara);

};

template <class T>
SearchAlgorithm<T>::SearchAlgorithm() {

}

template <class T>
SearchAlgorithm<T>::~SearchAlgorithm() {

}

// O(n)
template <class T>
int SearchAlgorithm<T>::busquedaSecuencial(std::vector<T> &A, T key, int &compara) {
  compara = 0;
  int i = 0;
  while (i < A.size() && A[i] != key) {
    compara++;
    i++;
  }
  if (i < A.size())
    return i;
  else
    return -1;
}

// O(n)
template <class T>
int SearchAlgorithm<T>::busquedaSecuencialVectorOrdenado(std::vector<T> &A, T key, int &compara) {
  compara = 0;
  for (int i = 0; i < A.size(); i++) {
    compara++;
    if (key <= A[i]) {
      compara++;
      if (key == A[i])
        return i;
      else
        return -1;
    }
  }
  return -1;
}

// O(log n)
template <class T>
int SearchAlgorithm<T>::busquedaBinaria(std::vector<T> &A, T key, int &compara) {
  int l = 0;
  int r = A.size() - 1;
  compara = 0;
  while (l <= r) {
    int m = l + (r - l) / 2;
    compara++;
    if (key == A[m])
      return m;
    else if (key < A[m])
      r = m - 1;
    else
      l = m + 1;
  }
  return -1;
}

// O(log n)
template <class T>
int SearchAlgorithm<T>::busquedaBinariaRecursiva(std::vector<T> &A, int low, int high, T key, int &compara) {
  if (low > high)
    return -1;
  int m = low + (high - low) / 2;
  compara++;
  if (key == A[m])
    return m;
  else if (key < A[m])
    return busquedaBinariaRecursiva(A, low, m-1, key, compara);
  else
    return busquedaBinariaRecursiva(A, m+1, high, key, compara);
}
#endif  // _SEARCH_ALGORITHM_H_