Package Util
Class Algo
java.lang.Object
Util.Algo
Provides static methods for efficient algorithmic operations
like binary search and ternary search on arrays and lists. It supports operations with
generic data types to compute insertion points (lower and upper bounds) or find
the minimum or maximum of a convex function
- Since:
- 1.0
- Version:
- 1.0
- Author:
- Sahasrad Chippa
-
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescriptionstatic <U extends Comparable<U>>
doublePerforms a ternary search on a double range to find a local maximum point in a convex or unimodal function.static <U extends Comparable<U>>
intPerforms a ternary search on an integer range to find a local maximum point in a convex or unimodal function.static <U extends Comparable<U>>
longPerforms a ternary search on a long range to find a local maximum point in a convex or unimodal function.static <U extends Comparable<U>>
doublePerforms a ternary search on a double range to find a local minimum point in a convex or unimodal function.static <U extends Comparable<U>>
intPerforms a ternary search on an integer range to find a local minimum point in a convex or unimodal function.static <U extends Comparable<U>>
longPerforms a ternary search on a long range to find a local minimum point in a convex or unimodal function.static double
getError()
Retrieves the current error tolerance for calculations involving double precision.static int
lowerBound
(char[] arr, char target) Finds the index of the first element in a sorted array of characters that is not less than the target character.static int
lowerBound
(double[] arr, double target) Finds the index of the first element in a sorted array of doubles that is not less than the target double.static int
lowerBound
(int[] arr, int target) Finds the index of the first element in a sorted array of integers that is not less than the target integer.static <U extends Comparable<U>>
intlowerBound
(int l, int r, U target, Function<Integer, U> function) Performs a parameterized binary search to find the smallest index where the target is not greater, comparing using a provided function.static int
lowerBound
(long[] arr, long target) Finds the index of the first element in a sorted array of longs that is not less than the target long.static <U extends Comparable<U>>
longlowerBound
(long l, long r, U target, Function<Long, U> function, long ignored) Performs a parameterized binary search using long indices to find the smallest index where the target is not greater, comparing using a provided function.static <U extends Comparable<U>>
intlowerBound
(List<U> list, U target) Finds the index of the first element in a sorted list of comparable elements that is not less than the target value using a lower bound binary search algorithm.static <U extends Comparable<U>>
intlowerBound
(U[] arr, U target) Finds the index of the first element in a sorted array that is not less than the target value using a lower bound binary search algorithm.static void
setError
(double error) Sets a new error tolerance for calculations involving double precision.static int
upperBound
(char[] arr, char target) Finds the index of the first element in the sorted array of characters that is greater than the target character.static int
upperBound
(double[] arr, double target) Finds the index of the first element in the sorted array of doubles that is greater than the target double.static int
upperBound
(int[] arr, int target) Finds the index of the first element in the sorted array of integers that is greater than the target integer.static <U extends Comparable<U>>
intupperBound
(int l, int r, U target, Function<Integer, U> function) Finds the index of the first element greater than the target using a custom function mapping integers to comparable items.static int
upperBound
(long[] arr, long target) Finds the index of the first element in the sorted array of longs that is greater than the target long.static <U extends Comparable<U>>
longupperBound
(long l, long r, U target, Function<Long, U> function, long ignored) Performs a binary search to find the upper bound (index of first element greater than the target) in a wider range specified using long indices.static <U extends Comparable<U>>
intupperBound
(List<U> list, U target) Finds the index of the first element in a sorted list that is greater than the target using an upper bound binary search algorithm.static <U extends Comparable<U>>
intupperBound
(U[] arr, U target) Finds the index of the first element in a sorted array that is greater than the target using an upper bound binary search algorithm.
-
Constructor Details
-
Algo
public Algo()
-
-
Method Details
-
lowerBound
public static <U extends Comparable<U>> int lowerBound(int l, int r, U target, Function<Integer, U> function) Performs a parameterized binary search to find the smallest index where the target is not greater, comparing using a provided function. Runs inO(log(n))
time assuming the provided function runs inO(1)
.- Type Parameters:
U
- Item type that is Comparable.- Parameters:
l
- The left boundary of the search interval (inclusive).r
- The right boundary of the search interval (exclusive).target
- The target element to search for.function
- Function converting an index to the comparable item of type U.- Returns:
- The lower bound index in terms of U.
-
lowerBound
public static <U extends Comparable<U>> long lowerBound(long l, long r, U target, Function<Long, U> function, long ignored) Performs a parameterized binary search using long indices to find the smallest index where the target is not greater, comparing using a provided function. Runs inO(log(n))
time assuming the compare operation and provided function run inO(1)
.- Type Parameters:
U
- Item type that is Comparable.- Parameters:
l
- The left boundary of the search interval (inclusive).r
- The right boundary of the search interval (exclusive).target
- The target element to search for.function
- Function converting a long index to the comparable item of type U.ignored
- Placeholder to differentiate between int and long method signatures.- Returns:
- The lower bound index in terms of U.
-
lowerBound
Finds the index of the first element in a sorted array that is not less than the target value using a lower bound binary search algorithm. Runs inO(log(n))
time assuming the compare operation runs inO(1)
.- Type Parameters:
U
- The type of elements in the array, which extends Comparable.- Parameters:
arr
- The sorted array of comparable elements.target
- The target value to compare against.- Returns:
- The index of the first element in the array that is not less than the target value.
-
lowerBound
public static int lowerBound(int[] arr, int target) Finds the index of the first element in a sorted array of integers that is not less than the target integer. Runs inO(log(n))
time.- Parameters:
arr
- The sorted array of integers.target
- The target integer to compare against.- Returns:
- The index of the first element in the array that is not less than the target integer.
-
lowerBound
public static int lowerBound(long[] arr, long target) Finds the index of the first element in a sorted array of longs that is not less than the target long. Runs inO(log(n))
time.- Parameters:
arr
- The sorted array of longs.target
- The target long to compare against.- Returns:
- The index of the first element in the array that is not less than the target long.
-
lowerBound
public static int lowerBound(double[] arr, double target) Finds the index of the first element in a sorted array of doubles that is not less than the target double. Runs inO(log(n))
time.- Parameters:
arr
- The sorted array of doubles.target
- The target double to compare against.- Returns:
- The index of the first element in the array that is not less than the target double.
-
lowerBound
public static int lowerBound(char[] arr, char target) Finds the index of the first element in a sorted array of characters that is not less than the target character. Runs inO(log(n))
time.- Parameters:
arr
- The sorted array of characters.target
- The target character to compare against.- Returns:
- The index of the first element in the array that is not less than the target character.
-
lowerBound
Finds the index of the first element in a sorted list of comparable elements that is not less than the target value using a lower bound binary search algorithm. Runs inO(log(n))
time assuming the compare operation runs inO(1)
.- Type Parameters:
U
- The type of elements in the list, which extends Comparable.- Parameters:
list
- The sorted list of comparable elements.target
- The target value to compare against.- Returns:
- The index of the first element in the list that is not less than the target value.
-
upperBound
public static <U extends Comparable<U>> int upperBound(int l, int r, U target, Function<Integer, U> function) Finds the index of the first element greater than the target using a custom function mapping integers to comparable items. This is a generic implementation of an upper bound binary search algorithm. Runs inO(log(n))
time assuming the compare operation and provided function run inO(1)
.- Type Parameters:
U
- The type of comparable items.- Parameters:
l
- The left boundary of the search interval (inclusive).r
- The right boundary of the search interval (exclusive).target
- The target value to find the upper bound for.function
- The function that maps from integer indices to U instances.- Returns:
- The index of the first element that is greater than the target.
-
upperBound
public static <U extends Comparable<U>> long upperBound(long l, long r, U target, Function<Long, U> function, long ignored) Performs a binary search to find the upper bound (index of first element greater than the target) in a wider range specified using long indices. Runs inO(log(n))
time assuming the compare operation and provided function run inO(1)
.- Type Parameters:
U
- The type of the elements being compared, which must be Comparable.- Parameters:
l
- The left boundary of the search interval (inclusive).r
- The right boundary of the search interval (exclusive).target
- The target value to compare against.function
- A function mapping long index values to comparable items.ignored
- A parameter used to distinguish this method signature.- Returns:
- The smallest index at which the elements are greater than the provided target.
-
upperBound
Finds the index of the first element in a sorted array that is greater than the target using an upper bound binary search algorithm. Runs inO(log(n))
time assuming the compare operation runs inO(1)
.- Type Parameters:
U
- The type of elements in the array, which extends Comparable.- Parameters:
arr
- The sorted array of comparable elements.target
- The target value to compare against.- Returns:
- The index of the first element in the array that is greater than the target value.
-
upperBound
public static int upperBound(int[] arr, int target) Finds the index of the first element in the sorted array of integers that is greater than the target integer. Runs inO(log(n))
time.- Parameters:
arr
- The sorted array of integers.target
- The target integer to compare against.- Returns:
- The index of the first element in the array that is greater than the target integer.
-
upperBound
public static int upperBound(long[] arr, long target) Finds the index of the first element in the sorted array of longs that is greater than the target long. Runs inO(log(n))
time.- Parameters:
arr
- The sorted array of longs.target
- The target long to compare against.- Returns:
- The index of the first element in the array that is greater than the target long.
-
upperBound
public static int upperBound(double[] arr, double target) Finds the index of the first element in the sorted array of doubles that is greater than the target double. Runs inO(log(n))
time.- Parameters:
arr
- The sorted array of doubles.target
- The target double to compare against.- Returns:
- The index of the first element in the array that is greater than the target double.
-
upperBound
public static int upperBound(char[] arr, char target) Finds the index of the first element in the sorted array of characters that is greater than the target character. Runs inO(log(n))
time.- Parameters:
arr
- The sorted array of characters.target
- The target character to compare against.- Returns:
- The index of the first element in the array that is greater than the target character.
-
upperBound
Finds the index of the first element in a sorted list that is greater than the target using an upper bound binary search algorithm. Runs inO(log(n))
time assuming the compare operation runs inO(1)
.- Type Parameters:
U
- The type of elements in the list, which extends Comparable.- Parameters:
list
- The sorted list of comparable elements.target
- The target value to compare against.- Returns:
- The index of the first element in the list that is greater than the target value.
-
convexMin
Performs a ternary search on an integer range to find a local minimum point in a convex or unimodal function. Runs inO(log(n))
time.- Type Parameters:
U
- The type of the elements being compared, which must extend Comparable.- Parameters:
l
- The left boundary index (inclusive).r
- The right boundary index (inclusive).function
- A function that maps an integer to a comparable item type U.- Returns:
- The index corresponding to the local minimum of the function.
-
convexMax
Performs a ternary search on an integer range to find a local maximum point in a convex or unimodal function. Runs inO(log(n))
time assuming the compare operation and provided function run inO(1)
.- Type Parameters:
U
- The type of the elements being compared, which must extend Comparable.- Parameters:
l
- The left boundary index (inclusive).r
- The right boundary index (inclusive).function
- A function that maps an integer to a comparable item type U.- Returns:
- The index corresponding to the local maximum of the function.
-
convexMin
public static <U extends Comparable<U>> long convexMin(long l, long r, Function<Long, U> function, long ignored) Performs a ternary search on a long range to find a local minimum point in a convex or unimodal function. Runs inO(log(n))
time assuming the compare operation and provided function run inO(1)
.- Type Parameters:
U
- The type of the elements being compared, which must extend Comparable.- Parameters:
l
- The left boundary index (inclusive).r
- The right boundary index (inclusive).function
- A function that maps a long index to a comparable item type U.ignored
- Placeholder parameter to distinguish method signature.- Returns:
- The index corresponding to the local minimum of the function.
-
convexMax
public static <U extends Comparable<U>> long convexMax(long l, long r, Function<Long, U> function, long ignored) Performs a ternary search on a long range to find a local maximum point in a convex or unimodal function. Runs inO(log(n))
time assuming the compare operation and provided function run inO(1)
.- Type Parameters:
U
- The type of the elements being compared, which must extend Comparable.- Parameters:
l
- The left boundary index (inclusive).r
- The right boundary index (inclusive).function
- A function that maps a long index to a comparable item type U.ignored
- Placeholder parameter to distinguish method signature.- Returns:
- The index corresponding to the local maximum of the function.
-
getError
public static double getError()Retrieves the current error tolerance for calculations involving double precision. The error tolerance is used in floating-point comparisons and controls the precision of the approximation in methods like convexMin and convexMax for double types.- Returns:
- The current error tolerance used in floating-point calculations.
-
setError
public static void setError(double error) Sets a new error tolerance for calculations involving double precision. This error defines the precision level for methods that deal with floating-point numbers and determines how close the approximation should be to the actual value. An error must be a non-negative value.- Parameters:
error
- The new error tolerance value to set, which cannot be negative.- Throws:
IllegalArgumentException
- if the specified error is negative.
-
convexMin
public static <U extends Comparable<U>> double convexMin(double l, double r, Function<Double, U> function, boolean ignored) Performs a ternary search on a double range to find a local minimum point in a convex or unimodal function. This method uses a predefined error tolerance to decide the precision of the result, seesetError(double)
. Theerror
defines how close the algorithm needs to approach the minimal value before stopping. Smaller values oferror
increase the precision but also increase computational demand. Runs inO(log(n))
time assuming the compare operation and provided function run inO(1)
.- Type Parameters:
U
- The type of elements being compared, which must extend Comparable.- Parameters:
l
- The left boundary value (inclusive).r
- The right boundary value (inclusive).function
- A function that maps a double to a comparable item type U.ignored
- Placeholder parameter to avoid method signature clashes.- Returns:
- The value corresponding to the local minimum of the function.
-
convexMax
public static <U extends Comparable<U>> double convexMax(double l, double r, Function<Double, U> function, boolean ignored) Performs a ternary search on a double range to find a local maximum point in a convex or unimodal function. This method uses a predefined error tolerance to decide the precision of the result, seesetError(double)
. Theerror
defines how close the algorithm needs to approach the maximal value before stopping. Smaller values oferror
increase the precision but also increase computational demand. Runs inO(log(n))
time assuming the compare operation and provided function run inO(1)
.- Type Parameters:
U
- The type of elements being compared, which must extend Comparable.- Parameters:
l
- The left boundary value (inclusive).r
- The right boundary value (inclusive).function
- A function that maps a double to a comparable item type U.ignored
- Placeholder parameter to avoid method signature clashes.- Returns:
- The value corresponding to the local maximum of the function.
-