com.abewy.backpack.util

Class SearchUtil

java.lang.Object

com.abewy.backpack.util.SearchUtil

public class SearchUtil
extends java.lang.Object

Field Summary

Fields

Modifier and Type	Field and Description
static int	NOT_FOUND

Constructor Summary

Constructors

Constructor and Description
SearchUtil()

Method Summary

Methods

Modifier and Type	Method and Description
static <T extends java.lang.Comparable<? super T>> int	binarySearch(java.util.List<T> l, T x) Search an object in an list of object using a binary search.
static <T extends java.lang.Comparable<? super T>> int	binarySearch(T[] a, T x) Search an object in an array of object using a binary search.
static int	maxSubSum(int[] a) Return the maximum sum of a consecutive sub sequence of the array

Methods inherited from class java.lang.Object

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

Field Detail

NOT_FOUND

public static final int NOT_FOUND

See Also:

Constant Field Values

Constructor Detail

SearchUtil

public SearchUtil()

Method Detail

binarySearch

public static <T extends java.lang.Comparable<? super T>> int binarySearch(T[] a,
                                                           T x)

Search an object in an array of object using a binary search.

Binary search is O(log N) complexity

The array must be sorted from lower to higher

Parameters:

a - the array to search in

x - the object to search for

Returns:

the index of the object, -1 if not found

binarySearch

public static <T extends java.lang.Comparable<? super T>> int binarySearch(java.util.List<T> l,
                                                           T x)

Search an object in an list of object using a binary search.

Binary search is O(log N) complexity

The list must be sorted from lower to higher

Parameters:

l - the list to search in

x - the object to search for

Returns:

the index of the object, -1 if not found

maxSubSum

public static int maxSubSum(int[] a)

Return the maximum sum of a consecutive sub sequence of the array

For exemple, consider the following array : -2 11, -4, 13, -5, -2.
Then the maximum sub sequence sum is 20 (11, -4, 13).

Parameters:

a - an array of integers (positive and negatives)

Returns:

the maximum sub sequence sum