DTL

Searching

Go back

Binary Search

Is an algorithm for finding an element's position in a sorted array/vector in logarithmic time and constant space.

Using Binary Search with DTL

#include "vector.hpp"
#include "binary_search.hpp"
#include <iostream>

int main() {
  dby::vector<int> vec = { 1, 2, 3, 6, 7, 9, 11, 12, 99 };

  std::cout << "POS -> VAL: 7 = " << dby::BinarySearch::recursive(vec, 7); // 4
  std::cout << "\nPOS -> VAL: 20 = " << dby::BinarySearch::recursive(vec, 20); // -1
  std::cout << "\nPOS -> VAL: 590 = " << dby::BinarySearch::recursive(vec, 590); // -1

  std::cout << "\nPOS -> VAL: 0 = " << dby::BinarySearch::iterative(vec, 0); // -1
  std::cout << "\nPOS -> VAL: 1 = " << dby::BinarySearch::iterative(vec, 1); // 0
  std::cout << "\nPOS -> VAL: 99 = " << dby::BinarySearch::iterative(vec, 99); // 8

  return 0;
}

Quick Select

Is a selection algorithm to find the k-th smallest o largest element in an unordered array or vector. It is related to the quick sort sorting algorithm.

Using Quick Select with DTL

#include "vector.hpp"
#include "quick_select.hpp"
#include <iostream>

int main() {
  dby::vector<int> vec = { 9, 8, 7, 6, 5, 4, 3, 2, 1 };

  std::cout << "1st smallest: " << dby::QuickSelect::kthSmallest(vec, 1); // 1
  std::cout << "\n2nd smallest: " << dby::QuickSelect::kthSmallest(vec, 2); // 2
  std::cout << "\n3rd smallest: " << dby::QuickSelect::kthSmallest(vec, 3); // 3
  std::cout << "\n20th smallest: " << dby::QuickSelect::kthSmallest(vec, 20); // -1

  std::cout << "\n\n1st largest: " << dby::QuickSelect::kthLargest(vec, 1); // 9
  std::cout << "\n5th largest: " << dby::QuickSelect::kthLargest(vec, 5); // 5
  std::cout << "\n9th largest: " << dby::QuickSelect::kthLargest(vec, 9); // 1
  std::cout << "\n20th largest: " << dby::QuickSelect::kthLargest(vec, 20); // -1

  return 0;
}