Chapter 12. Simple searches

// Data Structure & Algorithm C++, Otgonbayar Tovuudorj
// Chapter 12: Simple searches

// Sequential (Linear) search algorithm

#include <iostream>
#include <ctime>
#define N 20
using namespace std;

template <class keyType>
int seqSearch(keyType a[], keyType x, int n) {
  int i;
  for(i=0; i<n; i++)
    if(x == a[i]) return i;
  return -1;
}

int main() {
  int a[N], i;
  
  srand(time(0));
  for(i=0; i<N; i++) {
    a[i] = rand()%100;
    cout << a[i] << " ";
  }
  cout << "\nInput search key:"; cin >> i;
  i = seqSearch(a, i, N);
  
  if(i<0) cout << "not found\n";
  else cout << i << "th element\n";
}

// Data Structure & Algorithm C++, Otgonbayar Tovuudorj
// Chapter 12: Simple searches

// Sequential (Linear) search algorithm
// using recursion

#include <iostream>
#include <ctime>
#define N 20
using namespace std;

template <class keyType>
int seqSearch(keyType a[], keyType x, int n) {
  if(n<1) return -1;
  if(x == a[n-1]) return n-1;
  return seqSearch(a, x, n-1);
}

int main() {
  int a[N], i;
  
  srand(time(0));
  for(i=0; i<N; i++) {
    a[i] = rand()%100;
    cout << a[i] << " ";
  }
  cout << "\nInput search key:"; cin >> i;
  i = seqSearch(a, i, N);
  if(i<0) cout << "not found\n";
  else cout << i << "th element\n";
}

// Data Structure & Algorithm C++, Otgonbayar Tovuudorj
// Chapter 12: Simple searches

// Binary search algorithm

#include<iostream>
using namespace std;

template<class Type>
int binarySearch(Type a[], const Type x, int n) {
  int mid, low = 0, high = n;
  while (low <= high) {
    mid = (low + high)/2;
    if (x == a[mid]) return mid;
    if (x > a[mid]) low = mid + 1;
    else high = mid - 1;
  }
  return -1;
}

int main()
{
  int n=10, a[10] = {0, 2, 3, 5, 6, 7, 9, 12, 17, 21}, i, el;

  cout << "Sorted array: ";
  for(i=0; i<n; i++) cout << a[i] << " ";

  cout << endl << "Input search data: "; cin >> el;

  i = binarySearch(a, el, n-1);

  if (i != -1) cout << i << "-th element" << endl;
  else cout << "Not found." << endl;
}

// Data Structure & Algorithm C++, Otgonbayar Tovuudorj
// Chapter 12: Simple searches

// Binary search algorithm
// using recursion

#include<iostream>
using namespace std;

template<class Type>
int binarySearch(Type a[], const Type x, int high, int low=0) {
  if(low > high) return -1;
  else {
    int mid = (low + high)/2;
    if (x == a[mid]) return mid;
    else if (x > a[mid]) return binarySearch(a,x,high,mid+1);
    else return binarySearch(a,x,mid-1,low);
  }
}

int main()
{
  int n=10, a[10] = {0, 2, 3, 5, 6, 7, 9, 12, 17, 22}, i, el;

  cout << "Sorted array: ";
  for(i=0; i<n; i++) cout << a[i] << " ";

  cout << endl << "Input search data: "; cin >> el;

  i = binarySearch(a, el, n-1);

  if (i != -1) cout << i << "-th element" << endl;
  else cout << "Not found." << endl;

}