Агуулга: Энэ бүлэгт ашигласан программын кодуудыг энд үзүүллээ. Энэ бүлгээр бид маш бага хэмжээний өгөгдлийн хувьд үр ашигтай байх хайлтын зарим энгийн аргуудтай эхлэн танилцана.

Шугаман хайлт буюу дараалан хайх арга

1. хувилбар - I

// 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";
}

2. хувилбар - II рекүрсээр

// 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";
}

Хоёртын хайлт

1. хувилбар - I

// 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;
}

2. хувилбар - II рекүрсээр

// 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;

}