org.apache.commons.math3.utils
Class SearchIndexLibrary

java.lang.Object
  org.apache.commons.math3.utils.SearchIndexLibrary

public final class SearchIndexLibrary
extends Object

Index search algorithms based on method BinarySearch, coupled with dichotomy.
Contains two algorithms for both intervals conventions defined by ISearchIndex.SearchIndexIntervalConvention.
Also contains utility functions.

Since:

2.3.1

Version:

$Id: SearchIndexLibrary.java 11897 2015-01-08 15:24:11Z bignon $

Author:

Sophie Laurens

Concurrency :

immutable

Method Summary

static int	binarySearchClosedOpen(double[] tab, double key, int iMin, int iMax) Searches the index corresponding to the parameter key inside [tab[iMin], tab[iMax]] with the default convention CLOSED_OPEN, meaning that interval considered are [ tab[i], tab[i+1] [ and therefore, if x = tab[i], the integer returned is i.
static int	binarySearchOpenClosed(double[] tab, double key, int iMin, int iMax) Searches the index corresponding to the parameter key inside [tab[iMin], tab[iMax]] with the convention OPEN_CLOSED, meaning that interval considered are ] tab[i], tab[i+1] ] and therefore, if x = tab[i], the integer returned is i-1.
static int	midPoint(int iMin, int iMax) Returns the index of a middle point of segment [iMin, iMax]

Methods inherited from class java.lang.Object

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

Method Detail

midPoint

public static int midPoint(int iMin,
                           int iMax)

Returns the index of a middle point of segment [iMin, iMax]

Parameters:

iMin - : the lower bound of the interval

iMax - : the upper bound of the interval

Returns:

((iMax + iMin) / 2)

binarySearchClosedOpen

public static int binarySearchClosedOpen(double[] tab,
                                         double key,
                                         int iMin,
                                         int iMax)

Searches the index corresponding to the parameter key inside [tab[iMin], tab[iMax]] with the default convention CLOSED_OPEN, meaning that interval considered are [ tab[i], tab[i+1] [ and therefore, if x = tab[i], the integer returned is i. No exception is thrown if key does not belong to [tab[iMin], tab[iMax]].

Parameters:

tab - : the double[] already sorted.

key - : the double searched inside [tab[iMin], tab[iMax]]

iMin - : the lower bound of tab considered. If key < tab[iMin], the integer returned is iMin - 1

iMax - : the lower bound of tab considered. If key >=tab[iMax], the integer returned is iMax. As a consequence, a method using an index returned by binarySearchClosedOpen should consider two behavior if index = iMax. It can be either key = tab[iMax] or key > tab[iMax].

Returns:

index : an integer that belongs to [iMin - 1, iMax]

Preconditions :

the double[] tab is already sorted in an increasing order. Duplicates are allowed.

binarySearchOpenClosed

public static int binarySearchOpenClosed(double[] tab,
                                         double key,
                                         int iMin,
                                         int iMax)

Searches the index corresponding to the parameter key inside [tab[iMin], tab[iMax]] with the convention OPEN_CLOSED, meaning that interval considered are ] tab[i], tab[i+1] ] and therefore, if x = tab[i], the integer returned is i-1. No exception is thrown if key does not belong to [tab[iMin], tab[iMax]].

Parameters:

tab - : the double[] already sorted.

key - : the double searched inside [tab[iMin], tab[iMax]]

iMin - : the lower bound of tab considered. If key <= tab[iMin], the integer returned is iMin - 1

iMax - : the lower bound of tab considered. If key > tab[iMax], the integer returned is iMax. As a consequence, a method using an index returned by binarySearchClosedOpen should consider two behavior if index = iMin - 1. It can be either key = tab[iMin] or key < tab[iMin]

Returns:

index : an integer that belongs to [iMin - 1, iMax]

Preconditions :

the double[] tab is already sorted in an increasing order. Duplicates are allowed.