java - Java 中文本文件中的二分查找整数

Question

我在 txt 文件(公开在线托管)中有一个经过排序的整数列表，我需要要求用户提供一个数字，以便通过二分搜索在该整数列表中进行搜索。

我正在学习算法简介类(class)，而且我是 Java 新手。

使用我现在得到的代码，我收到以下错误:

Exception in thread "main" java.lang.IndexOutOfBoundsException: Index: 52, Size: 22
    at java.util.ArrayList.rangeCheck(Unknown Source)
    at java.util.ArrayList.get(Unknown Source)
    at BinSearch4.main(BinSearch4.java:67)

*while 循环(下面列出)是第 67 行

似乎无法弄清楚问题出在哪里。我也确信，即使是我正在做的一些事情也可以更有效地实现。任何人可以提供的任何帮助将不胜感激。

/*  Binary Search Algorithm
 * 
 * - Import a sorted list of integers of an unknown length
 * 
 * - Ask the user for a number to search for (searchValue)
 * 
 * - Run a Binary Search on the list of integers without simply using binarySearch
 * 
 * - Return the index of an occurrence of the search number (searchValue)
 * 
 * - Or -1 if the target is not found.
 * 
 * 
 */


import java.io.FileNotFoundException;
import java.io.IOException;
import java.net.URL;
import java.util.Scanner;
import java.util.ArrayList;

public class BinSearch4 {

public static void main(String[] args) throws IOException {

    URL url = new URL("http://m.uploadedit.com/ba3a/1423978916244.txt"); 
    ArrayList<Integer> arrList = new ArrayList<Integer>(); 
    int searchValue;
    int low;
    int high;
    int mid;
    int NOT_FOUND = -1;
    Scanner in = new Scanner(System.in);

    System.out.println("Enter your number to search for:");
    searchValue = in.nextInt(); 
    System.out.println(searchValue);

    try {

        Scanner scr = new Scanner(url.openStream()); 

        while (scr.hasNextLine()) {
            int i = scr.nextInt();
            arrList.add(i);
        }
        scr.close();
        System.out.println(arrList);


    }

    catch (FileNotFoundException e) {
        e.printStackTrace();
    }




    low = arrList.get(0);                      
    System.out.println(low);
    high = arrList.get(arrList.size() - 1);
    System.out.println(high);
    mid = (low + high) / 2;

    while (low <= high && arrList.get(mid) != searchValue) {
        if (arrList.get(mid) < searchValue) {
            low = mid + 1;
        } else  {
            high = mid - 1;
        }
        mid = (low + high) / 2;
    }
    if (low > high) {
        mid = NOT_FOUND;
    }
    System.out.println(mid);

 }
}

文本文件中的数字列表是: [-2、3、6、9、11、22、24、31、35、43、48、52、62、65、69、70、73、83、86、90、100、107]

Answer 1

二分查找

public class BinarySearch {

    public int binarySearch(int[] a) {
        int start = 0;
        int end = a.length - 1;
        int searchedValue = 70;

        for (int i = 0; i <= a.length; i++) {
            int mid = (start + end) / 2;

            if (searchedValue == a[mid]) {
                return 1;
            }

            if (searchedValue < a[mid]) {
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int a[] = { 2, 5, 40, 50, 60, 70 };
        BinarySearch binarySearch = new BinarySearch();
        System.out.println(binarySearch.binarySearch(a));
    }
}

开始必须为 0，结束为 arr.length-1