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

gkn4icbw 于 2021-07-06 发布在 Java

关注(0)|答案(1)|浏览(287)

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

import java.util.Scanner;
import java.util.Random;
import java.util.Arrays;

public class App {
  public static void main(String[] args) {
     Scanner scanner = new Scanner(System.in);

     System.out.println("\n" + " ");

    // generating n, 0 < n < 10000 and 0 < length < 100
     Random rand = new Random();
     int[] arr = new int[100];
     for (int z = 0; z < arr.length; z++) {
       arr[z] = rand.nextInt(10000);

     }
     // sorting 
     Arrays.sort(arr);
     System.out.println(Arrays.toString(arr));

     // binary search

     //pointers 
     int begin = 0;
     int last = arr.length - 1;
     int start = 0; 

     int x = scanner.nextInt();

     //loop
     while (begin <= last) {
      start = (begin + last) / 2;
      if (arr[start] < x) {
        begin = start + 1;
      }
      else if (arr[start] > x) {
        last = start - 1;
      }
      else {
        break;
      }
    }
    System.out.println("Element found at " + start);

}
}

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

Java

来源：https://stackoverflow.com/questions/64933928/how-do-i-implement-a-binary-search-for-finding-a-start-element-a-middle-element

1条答案

按热度按时间

ecbunoof1#

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

static int binarySearch(int[] arr, int begin, int last, int x) {
    int start = -1;
    boolean found = false;
    while (begin <= last) {
        start = (begin + last) / 2;
        if (arr[start] < x) {
            begin = start + 1;
        }
        else if (arr[start] > x) {
            last = start - 1;
        }
        else {
            found = true;
            break;
        }
    }
    System.out.printf("Element %d %s at index=%d%n", x, found ? "found" : "can be inserted at", start);
    return start;
}

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

//....
System.out.println("Input 3 numbers: ");
int[] inp = new int[3];

for (int i = 0; i < inp.length; i++) {
    inp[i] = scanner.nextInt();
}
Arrays.sort(inp);

for (int i = 0, start = 0; i < inp.length; i++) {
    start = binarySearch(arr, start, arr.length - 1, inp[i]);
}

样本输出：

[714, 726, 1016, 1108, 1124, 1221, 1291, 1316, 1394, 1412, 1455, 1557, 1604, 1674, 1737,
1893, 1961, 2105, 2243, 2258, 2266, 2318, 2337, 2545, 2608, 2740, 3029, 3066, 3077, 3097,
3155, 3159, 3257, 3262, 3587, 3602, 3609, 3745, 4155, 4380, 4497, 4517, 4529, 4576, 4902,
4943, 5029, 5103, 5302, 5364, 5504, 5572, 5750, 5820, 5902, 6033, 6043, 6222, 6240, 6271,
6357, 6358, 6359, 6369, 6384, 6447, 6598, 6657, 6687, 6720, 6834, 6905, 7082, 7106, 7133,
7144, 7426, 7436, 7451, 8232, 8286, 8320, 8402, 8444, 8511, 8591, 8680, 8801, 8895, 8994,
9074, 9133, 9162, 9315, 9403, 9607, 9691, 9691, 9893, 9957]

Input 3 numbers: 
15 726 9607
Element 15 can be inserted at at index=0
Element 726 found at index=1
Element 9607 found at index=95

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

int[] arr = new Random().ints(0, 10000).limit(100).sorted().toArray();

System.out.println(Arrays.toString(arr));

Scanner scanner = new Scanner(System.in);

System.out.println("Input 3 int numbers: ");

int[] start = new int[1];
IntStream.generate(scanner::nextInt)
         .limit(3)
         .sorted()
         .mapToObj(x -> Arrays.asList(x, start[0] = binarySearch(arr, start[0], arr.length - 1, x)))
         .forEach(res -> System.out.printf("index of %d is %d%n", res.get(0), res.get(1)));

赞(0）回复(0）举报 2021-07-06

我来回答

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

1条答案

相关问题

热门标签

最新问答