Algorithms_in_C++ 1.0.0
Set of algorithms implemented in C++.
Loading...
Searching...
No Matches
exponential_search.cpp File Reference

Exponential search algorithm More...

#include <cassert>
#include <cmath>
#include <iostream>
#include <cstring>
Include dependency graph for exponential_search.cpp:

Functions

template<class Type >
Type * binary_s (Type *array, size_t size, Type key)
 
template<class Type >
Type * struzik_search (Type *array, size_t size, Type key)
 
int main ()
 

Detailed Description

Exponential search algorithm

The algorithm try to search the range where the key should be. If it has been found we do a binary search there. The range of the search grows by exponential every time. If the key is larger than the last element of array, the start of block(block_front) will be equal to the end of block(block_size) and the algorithm return null ponter, every other cases the algoritm return fom the loop.

Function Documentation

◆ binary_s()

template<class Type >
Type * binary_s ( Type * array,
size_t size,
Type key )
inline

Binary Search Algorithm (used by struzik_search)

  • Time Complexity O(log n) where 'n' is the number of elements
  • Worst Time Complexity O(log n)
  • Best Time Complexity Ω(1)
  • Space Complexity O(1)
  • Auxiliary Space Complexity O(1)
    Returns
    pointer to value in the array
    nullptr if value not found
34 {
35 int32_t lower_index(0), upper_index(size - 1), middle_index;
36
37 while (lower_index <= upper_index) {
38 middle_index = std::floor((lower_index + upper_index) / 2);
39
40 if (*(array + middle_index) < key)
41 lower_index = (middle_index + 1);
42 else if (*(array + middle_index) > key)
43 upper_index = (middle_index - 1);
44 else
45 return (array + middle_index);
46 }
47
48 return nullptr;
49}
T floor(T... args)
Here is the call graph for this function:

◆ main()

int main ( void )

Main function

74 {
75 // TEST CASES
76 int* sorted_array = new int[7]{7, 10, 15, 23, 70, 105, 203};
77 assert(struzik_search<int>(sorted_array, 7, 0) == nullptr);
78 assert(struzik_search<int>(sorted_array, 7, 1000) == nullptr);
79 assert(struzik_search<int>(sorted_array, 7, 50) == nullptr);
80 assert(struzik_search<int>(sorted_array, 7, 7) == sorted_array);
81 // TEST CASES
82 delete[] sorted_array;
83 return 0;
84}

◆ struzik_search()

template<class Type >
Type * struzik_search ( Type * array,
size_t size,
Type key )

Struzik Search Algorithm(Exponential)

  • Time Complexity O(log i) where i is the position of search key in the list
  • Worst Time Complexity O(log i)
  • Best Time Complexity Ω(1)
  • Space Complexity O(1)
  • Auxiliary Space Complexity O(1)
59 {
60 uint32_t block_front(0), block_size = size == 0 ? 0 : 1;
61 while (block_front != block_size) {
62 if (*(array + block_size - 1) < key) {
63 block_front = block_size;
64 (block_size * 2 - 1 < size) ? (block_size *= 2) : block_size = size;
65 continue;
66 }
67 return binary_s<Type>(array + block_front, (block_size - block_front),
68 key);
69 }
70 return nullptr;
71}