Last active
August 10, 2023 21:10
-
-
Save odds-get-evened/78cc6fc6f6583c6998725571c6478fbd to your computer and use it in GitHub Desktop.
a modernized version of Sedgewik's BinarySearch class
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package algorithm; | |
import org.apache.commons.lang.ArrayUtils; | |
import java.security.SecureRandom; | |
import java.util.Arrays; | |
import java.util.stream.IntStream; | |
import static java.lang.System.out; | |
/** | |
* Provides a static method for binary | |
* searching for an integer in a sorted array of integers | |
* | |
* command arguments <min int> <max int> <array length> <desired index> | |
*/ | |
public class BinarySearch { | |
// do not allow instantiation of this class | |
private BinarySearch() {} | |
/** | |
* @param a the array of integers, must be sorted in ascending order | |
* @param key the search key | |
* @return index of the key in array if present, otherwise -1 | |
*/ | |
public static int indexOf(int[] a, int key) { | |
int lo = 0; | |
int hi = a.length - 1; | |
while(lo <= hi) { // when lo meets hi BINGO! | |
// key is in a[lo..hi] or not present | |
int mid = lo + (hi - lo) / 2; | |
if (key < a[mid]) hi = mid - 1; // lower the top end by 1 | |
else if (key > a[mid]) lo = mid + 1; // raise the low end by 1 | |
else return mid; | |
} | |
return -1; | |
} | |
public static void main(String[] args) { | |
// generate random numbers between min and max with length of n | |
int min; | |
int max; | |
int n = 16; | |
int l = 5; | |
/** | |
* 4 args here, range min, range max, length of array, | |
* and desired index from the array. | |
*/ | |
if(args.length == 4) { // if user supplies 3 integers (min, max, length, index) | |
min = Integer.parseInt(args[0].trim()); | |
max = Integer.parseInt(args[1].trim()); | |
n = Integer.parseInt(args[2].trim()); | |
l = Integer.parseInt(args[3].trim()); | |
} else { | |
max = 99; | |
min = 10; | |
} | |
// smooooth. generates an array of random integers of a specified length | |
int[] randoCalrissian = IntStream.generate(() -> (new SecureRandom()).nextInt(min, max)) | |
.limit(n) | |
.toArray(); | |
Arrays.sort(randoCalrissian); | |
out.println(ArrayUtils.toString(randoCalrissian, "")); | |
// search for index 5 | |
if(BinarySearch.indexOf(randoCalrissian, l) == -1) | |
try { | |
out.println(randoCalrissian[l]); | |
} catch (ArrayIndexOutOfBoundsException e) { | |
out.printf("your index selection of %d is out of bounds (%d, %d).", l, min, max); | |
System.exit(-1); | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment