com.sl.algorithms.search.binarysearch

Class RecursiveBinarySearch<T extends java.lang.Comparable>

java.lang.Object

com.sl.algorithms.search.binarysearch.RecursiveBinarySearch<T>

All Implemented Interfaces:

BaseInterface<T>, Constants, Search<T>

public class RecursiveBinarySearch<T extends java.lang.Comparable>
extends java.lang.Object
implements Search<T>

Objective: Search in a SORTED array, in Logarithmic time.

Reference

Field Summary

Fields inherited from interface com.sl.algorithms.core.interfaces.base.Constants

ARRAY_IS_EMPTY, DATA_TYPE_NOT_SUPPORTED_YET, DECIMAL_RADIX, DELIMITER_COMMA, ELEMENT_NOT_FOUND, LIST_IS_EMPTY, OPERATION_NOT_SUPPORTED_YET

Constructor Summary

Constructors

Constructor and Description
RecursiveBinarySearch()

Method Summary

Modifier and Type	Method and Description
int	findIndex(T[] sortedInput, T targetElement) Since we reduce the search space by half each time, the complexity must be in the order of O(log(n)). O(log(n)) time and space. Linear space complexity because of the implicit recursion stack.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Methods inherited from interface com.sl.algorithms.core.interfaces.base.BaseInterface

checkArray, checkIntArray, checkList

Constructor Detail

RecursiveBinarySearch

public RecursiveBinarySearch()

Method Detail

findIndex

public int findIndex(T[] sortedInput,
                     T targetElement)

Since we reduce the search space by half each time, the complexity must be in the order of O(log(n)).

O(log(n)) time and space.

Linear space complexity because of the implicit recursion stack.

Specified by:

findIndex in interface Search<T extends java.lang.Comparable>