如何实现二进制搜索来查找开始元素、中间元素和结束元素?java

gkn4icbw  于 2021-07-06  发布在  Java
关注(0)|答案(1)|浏览(301)

我正在创建一个程序,允许用户输入3个数字,这些数字将在排序数组中找到,索引将使用二进制搜索返回。
我已经对数组进行了排序,并对一个用户输入进行了二进制搜索。如何实现查找三个数字?开始数字、中间数字和结束数字。
我提供了代码、输入和输出。
代码:

  1. import java.util.Scanner;
  2. import java.util.Random;
  3. import java.util.Arrays;
  4. public class App {
  5. public static void main(String[] args) {
  6. Scanner scanner = new Scanner(System.in);
  7. System.out.println("\n" + " ");
  8. // generating n, 0 < n < 10000 and 0 < length < 100
  9. Random rand = new Random();
  10. int[] arr = new int[100];
  11. for (int z = 0; z < arr.length; z++) {
  12. arr[z] = rand.nextInt(10000);
  13. }
  14. // sorting
  15. Arrays.sort(arr);
  16. System.out.println(Arrays.toString(arr));
  17. // binary search
  18. //pointers
  19. int begin = 0;
  20. int last = arr.length - 1;
  21. int start = 0;
  22. int x = scanner.nextInt();
  23. //loop
  24. while (begin <= last) {
  25. start = (begin + last) / 2;
  26. if (arr[start] < x) {
  27. begin = start + 1;
  28. }
  29. else if (arr[start] > x) {
  30. last = start - 1;
  31. }
  32. else {
  33. break;
  34. }
  35. }
  36. System.out.println("Element found at " + start);
  37. }
  38. }

我想让它尽可能简单。谢谢。

ecbunoof

ecbunoof1#

你应该提取 binarySearch 将函数转换为单独的方法,并在循环中调用此方法。
如果在数组中找到确切的元素,或者检测到插入点,也可以打印。

  1. static int binarySearch(int[] arr, int begin, int last, int x) {
  2. int start = -1;
  3. boolean found = false;
  4. while (begin <= last) {
  5. start = (begin + last) / 2;
  6. if (arr[start] < x) {
  7. begin = start + 1;
  8. }
  9. else if (arr[start] > x) {
  10. last = start - 1;
  11. }
  12. else {
  13. found = true;
  14. break;
  15. }
  16. }
  17. System.out.printf("Element %d %s at index=%d%n", x, found ? "found" : "can be inserted at", start);
  18. return start;
  19. }

测试循环:用户输入数组被强制排序, start 在以下每次迭代中更新:

  1. //....
  2. System.out.println("Input 3 numbers: ");
  3. int[] inp = new int[3];
  4. for (int i = 0; i < inp.length; i++) {
  5. inp[i] = scanner.nextInt();
  6. }
  7. Arrays.sort(inp);
  8. for (int i = 0, start = 0; i < inp.length; i++) {
  9. start = binarySearch(arr, start, arr.length - 1, inp[i]);
  10. }

样本输出:

  1. [714, 726, 1016, 1108, 1124, 1221, 1291, 1316, 1394, 1412, 1455, 1557, 1604, 1674, 1737,
  2. 1893, 1961, 2105, 2243, 2258, 2266, 2318, 2337, 2545, 2608, 2740, 3029, 3066, 3077, 3097,
  3. 3155, 3159, 3257, 3262, 3587, 3602, 3609, 3745, 4155, 4380, 4497, 4517, 4529, 4576, 4902,
  4. 4943, 5029, 5103, 5302, 5364, 5504, 5572, 5750, 5820, 5902, 6033, 6043, 6222, 6240, 6271,
  5. 6357, 6358, 6359, 6369, 6384, 6447, 6598, 6657, 6687, 6720, 6834, 6905, 7082, 7106, 7133,
  6. 7144, 7426, 7436, 7451, 8232, 8286, 8320, 8402, 8444, 8511, 8591, 8680, 8801, 8895, 8994,
  7. 9074, 9133, 9162, 9315, 9403, 9607, 9691, 9691, 9893, 9957]
  8. Input 3 numbers:
  9. 15 726 9607
  10. Element 15 can be inserted at at index=0
  11. Element 726 found at index=1
  12. Element 9607 found at index=95

基于流的解决方案更简洁:
使用随机整数流 Random::ints 使用 IntStream.generate 通过方法引用获取用户输入 Scanner::nextInt 使用排序流 sorted 方法
需要使用一个1元素数组来存储 start 把它传给 binarySearch 方法。

  1. int[] arr = new Random().ints(0, 10000).limit(100).sorted().toArray();
  2. System.out.println(Arrays.toString(arr));
  3. Scanner scanner = new Scanner(System.in);
  4. System.out.println("Input 3 int numbers: ");
  5. int[] start = new int[1];
  6. IntStream.generate(scanner::nextInt)
  7. .limit(3)
  8. .sorted()
  9. .mapToObj(x -> Arrays.asList(x, start[0] = binarySearch(arr, start[0], arr.length - 1, x)))
  10. .forEach(res -> System.out.printf("index of %d is %d%n", res.get(0), res.get(1)));
展开查看全部

相关问题