com.sl.algorithms.search.binarysearch

Class IterativeBinarySearch<T extends java.lang.Comparable>

java.lang.Object

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

All Implemented Interfaces:

BaseInterface<T>, Constants, Search<T>

public class IterativeBinarySearch<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
IterativeBinarySearch()

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 O(1) space.
protected int	findIndexIteratively(T[] sortedInput, T itemToSearch, int start, int end)

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

IterativeBinarySearch

public IterativeBinarySearch()

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 O(1) space.

Specified by:

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

findIndexIteratively

protected int findIndexIteratively(T[] sortedInput,
                                   T itemToSearch,
                                   int start,
                                   int end)