saddleback_search.cpp File Reference

Implementation of Saddleback Algorithm for 2D arrays. More...

#include <cassert>
#include <cstdint>
#include <iostream>
#include <vector>

Include dependency graph for saddleback_search.cpp:

Go to the source code of this file.

Namespaces
namespace	search
	for std::assert
namespace	saddleback
	Function for implementing Saddleback Algorithm.

Functions
std::pair< uint32_t, uint32_t >	search::saddleback::saddleback (std::vector< std::vector< int32_t > > matrix, int32_t element)
static void	test ()
	Test implementations.
int	main ()
	Main function.

Detailed Description

Implementation of Saddleback Algorithm for 2D arrays.

Saddleback Algorithm is an algorithm that searches 2D array in linear time, i.e, O(m + n), where m is number of rows and n is number of columns of 2D array. Also, each row and column of the matrix should be sorted beforehand for this algorithm to work.

Author

Hashir Niazi

Definition in file saddleback_search.cpp.

Function Documentation

main()

int main

(

void

)

Main function.

Returns

0 on exit

Definition at line 112 of file saddleback_search.cpp.

           {
    test();  // execute the tests
    return 0;
}

saddleback()

std::pair< uint32_t, uint32_t > search::saddleback::saddleback	(	std::vector< std::vector< int32_t > >	matrix,
		int32_t	element )

This function implements Saddleback Algorithm, on a sorted 2D array, and finds the location of the element needed to search

Parameters

matrix	2D matrix which is sorted on the basis of rows and columns
element	element to be searched

Returns

An std::pair of with row and column populated within it, if the element is present.

An std::pair with (0, 0), if the element is not present.

Definition at line 39 of file saddleback_search.cpp.

                                                           {
    uint32_t left_index = 0;
    uint32_t right_index = matrix[0].size() - 1;  // Start from top right corner
    while (left_index <
           matrix.size()) {  // Exit once the value of indexes get out of range.
        if (element ==
            matrix[left_index]
                  [right_index]) {  // If value on this position of matrix is
                                    // equal to element, return (row, column).
            return std::make_pair(left_index + 1, right_index + 1);
        } else if (element >
                   matrix[left_index]
                         [right_index]) {  // Else if value on this position of
                                           // matrix is less than the element,
                                           // move left.
            ++left_index;
        } else if (element <
                   matrix[left_index]
                         [right_index]) {  // Else if value on this position of
                                           // matrix is greater than the
                                           // element, move down.
            if (!right_index)
                break;
            else
                --right_index;
        }
    }
    return std::make_pair(
        0, 0);  // If the program reaches here, that means one of the index
                // went out of index, hence no element present.
}

test()

static void test ( )

static

Test implementations.

Returns

void

Definition at line 78 of file saddleback_search.cpp.

                   {
    std::vector<std::vector<int32_t>> matrix = {{1, 10, 100, 1000, 10000},
                                                {2, 20, 200, 2000, 20000},
                                                {3, 30, 300, 3000, 30000},
                                                {4, 40, 400, 4000, 40000},
                                                {5, 50, 500, 5000, 50000}};
 
    std::pair<uint32_t, uint32_t> not_found = std::make_pair(0, 0);
    std::pair<uint32_t, uint32_t> test_answer;
    // Test 1
    std::pair<uint32_t, uint32_t> answer1 =
        search::saddleback::saddleback(matrix, 123);
    assert(not_found == answer1);
    // Test 2
    answer1 = search::saddleback::saddleback(matrix, 0);
    assert(not_found == answer1);
    // Test 3
    answer1 = search::saddleback::saddleback(matrix, 1);
    test_answer = std::make_pair(1, 1);
    assert(test_answer == answer1);
    // Test 4
    answer1 = search::saddleback::saddleback(matrix, 50000);
    test_answer = std::make_pair(5, 5);
    assert(test_answer == answer1);
    // Test 5
    answer1 = search::saddleback::saddleback(matrix, 300);
    test_answer = std::make_pair(3, 3);
    assert(test_answer == answer1);
}