common search algorithms #searching

README.md

Common search techniques

• Binary search
• Interpolation search
• Fibonacci search

TO-DO

• Fix Floating point exception in interpolation search
• Implement a recursive version of Fibonacci search
• Implement a Fibonacci search by checking array length with Fn instead of Fn - 1
  • please see references
• Implement an alternative approach by replacing FibonacciValues with Fibonacci array
• Implement Knuth's and wiki's approach

References

• Fibonacci Search
• Ulf Leser's slides
• Fibonaccian search in C
• Fibonacci Search Algorithm, written in C

binary_search.cpp

#include <cassert>
#include "search.h"

// If the types of left and right are unsigned int, then
// right = middle - 1 or left = middle + 1 may overflow!
int recursiveBinarySearch(int list[], int left, int right, int key)
{
  if (left > right) {
    return NOT_FOUND;
  }

  int middle = left + (right - left)/2;

  if (list[middle] == key) {
    return middle;
  } else if (list[middle] > key) {
    right = middle - 1;
    // assert(right < middle);
  } else { // list[middle] < key
    left = middle + 1;
    // assert(left > middle);
  }
  return recursiveBinarySearch(list, left, middle - 1, key);
}

int iterativeBinarySearch(int list[], int left, int right, int key)
{
  int middle;
  while (left <= right) {
    middle = left + (right - left)/2;

    if (list[middle] == key) {
      return middle;
    } else if (list[middle] > key) {
      right = middle - 1;
      // assert(right < middle);
    } else { // list[middle] < key
      left = middle + 1;
      // assert(left > middle);
    }
  }

  return NOT_FOUND;
}

int binarySearch(int list[], unsigned int length, int key)
{
  assert(list && length);
  // return recursiveBinarySearch(list, 0, length - 1, key);
  return iterativeBinarySearch(list, 0, length - 1, key);
}

fibonacci_search.cpp

#include <algorithm>
#include <cassert>
#include "search.h"

typedef struct FibonacciValues
{
  // Fibonacci number: F(n) = F(n-1) + F(n-2)
  int Fn_2; // F(n-2)
  int Fn_1; // F(n-1)
  int Fn;   // F(n)

  FibonacciValues(int fn_2, int fn_1, int fn)
    : Fn_2(fn_2)
    , Fn_1(fn_1)
    , Fn(fn)
  {
    assert(Fn == Fn_1 + Fn_2);
  }

  ~FibonacciValues()
  {
  }

  void forward()
  {
    Fn_2 = Fn_1;
    Fn_1 = Fn;
    Fn = Fn_1 + Fn_2;
    assert(Fn == Fn_1 + Fn_2);
  }

  void backward()
  {
    Fn = Fn_1;
    Fn_1 = Fn_2;
    Fn_2 = Fn - Fn_1;
    assert(Fn == Fn_1 + Fn_2);
  }

} FibonacciValues;

// Returns the smallest Fibonacci number that is greater than or equal to k.
FibonacciValues GetFibonacci(int k)
{
  FibonacciValues fib(0, 1, 1);
  while (fib.Fn < k) {
    fib.forward();
  }
  return fib;
}


// |<---------             p: F(n) - 1             --------->|
// |<---    q: F(n-1) - 1    --->|   |<--  r: F(n-2) - 1  -->|
// +----+---+--------------------+---+---+---+---+
// |    | k |                    | m |   | k |   |
// +----+---+--------------------+---+---+---+---+
//                                 ^
//    F(n) = F(n-1) + F(n-2)
// => F(n) - 1 = [ F(n-1) - 1 ] + 1 + [ F(n-2) - 1 ]
// The '1' here is for the middle item(the 'm' in above figure).
//
// If k < m, then search key in q = F(n-1) - 1:
//
// |<---    p: F(n-1) - 1    --->|
// |<----- q ----->|   |<-- r -->|
// +----+---+------+---+---------+
// |    | k |      | m |         |
// +----+---+------+---+---------+
//
// Set p = F(n-1) - 1, q = F(n-2) - 1, r = F(n-3) - 1 and repeat the process.
// => Fibonacci numbers go backward once.
//
// If k > m, then repeat then search key in r = F(n-2) - 1:
//
// |<--  p: F(n-2) - 1  -->|
// |<--- q --->|   |<- r ->|
// +---+---+---+
// |   | k |   | m
// +---+---+---+
//               ^
// Set p = F(n-2) - 1, q = F(n-3) - 1, r = F(n-4) - 1 and repeat the process.
// => Fibonacci numbers go backward twice.
//
// Notice that the current middle might exceed the array!

int fibonacciSearch(int list[], const unsigned int length, int key)
{
  assert(list && length);

  int left = 0, right = length - 1, middle;
  // Find a fibonacci number F(n) that F(n) - 1 >= length
  FibonacciValues fib = GetFibonacci(length + 1);

  while (left <= right) {
    // Avoid the middle is over the array.
    middle = std::min(left + (fib.Fn_1 - 1), right);

    if (list[middle] == key) {
      return middle;
    } else if (list[middle] > key) {
      right = middle - 1;
      fib.backward();
    } else { // list[middle] < key
      left = middle + 1;
      fib.backward(); fib.backward();
    }
  }

  return NOT_FOUND;
}

interpolation_search.cpp

#include <cassert>
#include "search.h"

//   Value
//     ^
//     |
// max +-----------------*
//     |                /|
//     |               / |
//     |              /  |
//     |             /   |
//     |            /    |
//     |           /     |
// key +----------*      |
//     |         /|      |
//     |        / |      |
//     |       /  |      |
//     |      /   |      |
//     |     /    |      |
//     |    /     |      |
// min +---*      |      |
//     |   |      |      |
//     |   |      |      |
//     |   |      |      |
//     |   |      |      |
//     +---+------+------+---> Index
//        I_min  I_key   I_max
//
// (I_key - I_min) / (key - min) = (I_max - I_min) / (max - min)
// I_key = I_min + (key - min) * (I_max - I_min) / (max - min)
//
// The interpolation search is similar to binary search.
// The difference is that the 'middle' is replaced by the 'I_key' above.
// Also, we need to make sure: min <= value at I_key <= max
// If the condition doesn't meet, than we break the loop.
// Otherwise, the process may repeat forever.
// Let's see an example below:
//
// Index   0   1   2   3   4   5
// Data  -10   4  10  30  32  40
//
// Example: Search key 25
// 1) L: 0, R: 5 -> m: Data[L] = -10, M: Data[R] = 40
//
//    idx = Floor( L + (key - m) * (R - L) / (M - m) )
//        = Floor( 0 + 35 * 5 / 50 ) = Floor( 3.5 ) = 3
//
//    Data[idx] = 30 > key = 25 => R = idx - 1 = 2
//
//    Now, the key = 25 is already larger than Data[R] = 20.
//    We should stop processing here.
//    Otherwise, the process will repeat forever.
//
//
// 2) L: 0, R: 2 -> m: Data[L] = -10, M: Data[R] = 10
//
//    idx = Floor( L + (key - m) * (R - L) / (M - m) )
//        = Floor( 0 + 35 * 2 / 20 ) = Floor( 3.5 ) = 3
//
//    Data[idx] = 30 > key = 25 => R = idx - 1 = 2
//
// 3) L: 0, R: 2 -> m: Data[L] = -10, M: Data[R] = 10
//
//    Repeat 2's process .....
//
int recursiveInterpolationSearch(int list[], int left, int right, int key)
{
  int min = list[left];
  int max = list[right];

  if (left > right || key < min || key > max) {
    return NOT_FOUND;
  }

  int middle = left + (key - min) * (right - left) / (max - min);

  if (key == list[middle]) {
    return middle;
  } else if (list[middle] > key) {
    right = middle - 1;
  } else { // list[middle] < key
    left = middle + 1;
  }
  return recursiveInterpolationSearch(list, left, right, key);
}

int iterativeInterpolationSearch(int list[], int left, int right, int key)
{
  int middle;
  int min = list[left], max = list[right];
  // Make sure min <= key <= max, or middle will be < left or > right
  while(left <= right && key >= min && key <= max) {
    min = list[left];
    max = list[right];
    middle = left + (key - min) * ((right - left) / (max - min));

    if (key == list[middle]) {
      return middle;
    } else if (list[middle] > key) {
      right = middle - 1;
    } else { // list[middle] < key
      left = middle + 1;
    }
  }

  return NOT_FOUND;
}

int interpolationSearch(int list[], const unsigned int length, int key)
{
  assert(list && length);
  // return recursiveInterpolationSearch(list, 0, length - 1, key);
  return iterativeInterpolationSearch(list, 0, length - 1, key);
}

makefile

CC=g++
CFLAGS=-Wall --std=c++11

SOURCES=test.cpp\
        binary_search.cpp\
        fibonacci_search.cpp\
        interpolation_search.cpp
OBJECTS=$(SOURCES:.cpp=.o)

# Name of the executable program
EXECUTABLE=run_test

all: $(EXECUTABLE)

# $@ is same as $(EXECUTABLE)
$(EXECUTABLE): $(OBJECTS)
	$(CC) $(CFLAGS) $(OBJECTS) -o $@

# ".cpp.o" is a suffix rule telling make how to turn file.cpp into file.o
# for an arbitrary file.
#
# $< is an automatic variable referencing the source file,
# file.cpp in the case of the suffix rule.
#
# $@ is an automatic variable referencing the target file, file.o.
# file.o in the case of the suffix rule.
#
# Use -c to generatethe .o file
.cpp.o:
	$(CC) -c $(CFLAGS) $< -o $@

clean:
	rm *.o $(EXECUTABLE)

search.h

#ifndef SEARCH_H
#define SEARCH_H

const int NOT_FOUND = -1;

int binarySearch(int list[], unsigned int length, int key);

int interpolationSearch(int list[], unsigned int length, int key);

int fibonacciSearch(int list[], unsigned int length, int key);

#endif // SEARCH_H

test.cpp

#include <cassert>
#include <iostream>
#include <random>

#include "search.h"

using std::cout;
using std::endl;

using std::random_device;
using std::default_random_engine;
using std::uniform_int_distribution;

random_device RandDev;
default_random_engine RandEng(RandDev());

int getRandom(int min, int max)
{
  uniform_int_distribution<int> uniDist(min, max);
  return uniDist(RandEng);
}

void generateList(int list[], unsigned int length, int min, int max, int minInterval)
{
  int avgInterval = (max - min)/length;
  assert(minInterval > 0 && avgInterval > minInterval);
  int interval;
  for (unsigned int i = 0 ; i < length ; i++) {
    interval = getRandom(minInterval, 2 * avgInterval);
    if (!i) {
      list[i] = interval + min;
      continue;
    }

    if (list[i-1] + minInterval >= max) {
      list[i] = max;
      continue;
    }

    list[i] = list[i-1] + interval;
    if (list[i] > max) {
      list[i] = list[i-1] + minInterval;
    }
  }
}

void printList(int list[], unsigned int length)
{
  for (unsigned int i = 0 ; i < length ; i++) {
    cout << list[i] << " ";
  }
  cout << endl;
}

int main()
{
  const int length = 10;
  int list[length] = { 0 };
  const int min = -100, max = 100, minInterval = 2;
  generateList(list, length, min, max, minInterval);

  cout << "List: ";
  printList(list, length);

  int result = NOT_FOUND;
  int index = getRandom(0, length - 1); // Get a random number from [0, length)

  cout << "\t Find " << list[index] << " in ";
  result = binarySearch(list, length, list[index]);
  assert(list[index] == list[result]);
  result = interpolationSearch(list, length, list[index]);
  assert(list[index] == list[result]);
  cout << result << endl;
  result = fibonacciSearch(list, length, list[index]);
  assert(list[index] == list[result]);

  assert(minInterval - 1 > 0);
  int inexistence = list[index] - 1;

  cout << "\t Try finding " << inexistence << ": ";
  result = binarySearch(list, length, inexistence);
  assert(result == NOT_FOUND);
  result = interpolationSearch(list, length, inexistence);
  assert(result == NOT_FOUND);
  result = fibonacciSearch(list, length, inexistence);
  assert(result == NOT_FOUND);
  cout << "not found!" << endl;

  return 0;
}