Java中Binary Search查询姓名时返回随机负值的问题求助

核心原因分析 #

• 输入读取不完整，导致查询key不匹配
  你在读取姓名时使用了in.next()方法，该方法只会读取到第一个空白字符（空格、换行、制表符等）就停止。如果你的姓名包含空格（比如"张三 三"），或者输入的姓名是完整一行内容，in.next()只能获取到部分内容，和names列表中存储的完整姓名key无法匹配，最终导致二分查找失败，返回负索引。

• 输入缓冲区残留换行符的干扰
  在读取电话号码时使用in.next()后，输入缓冲区中会残留换行符。如果直接继续读取姓名，即使next()会跳过前导空白，也可能导致读取到不符合预期的内容，进一步加剧查找失败的概率。

修复后的代码 #

import java.io.File;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;
import java.io.FileNotFoundException;

public class Test 
{
    public static void main(String[] args) throws FileNotFoundException
    {
        File inputFile = new File("directory.txt");
        ArrayList<Item> names = new ArrayList<Item>();
        ArrayList<Item> numbers = new ArrayList<Item>();
        
        Scanner in1 = new Scanner(inputFile);
        while(in1.hasNextLine())
        {
            String name = in1.nextLine();
            String num = in1.nextLine();
            Item item = new Item(name , num);
            names.add(item);
        }
        
        Scanner in2 = new Scanner(inputFile);
        while(in2.hasNextLine())
        {
            String name = in2.nextLine();
            String num = in2.nextLine();
            Item item = new Item(num, name);
            numbers.add(item);
        }
        
        Collections.sort(names);
        Collections.sort(numbers);
        
        Scanner in = new Scanner(System.in);
        
        System.out.println("Enter number: ");
        String num = in.next();
        // 消耗掉next()后残留的换行符
        in.nextLine();
        int index = Collections.binarySearch(numbers, new Item(num, null));
        if (index >= 0) {
            System.out.println(index);
            System.out.println(numbers.get(index).getValue()); 
        } else {
            System.out.println("号码不存在");
        }
        
        System.out.println("Enter name: ");
        String name = in.nextLine();
        index = Collections.binarySearch(names, new Item(name, null));
        if (index >= 0) {
            System.out.println(index);
            System.out.println(names.get(index).getValue());
        } else {
            System.out.println("姓名不存在");
        }
    }
}

class Item implements Comparable<Item>
{ 
    public Item(String k, String v)
    { 
        key = k;
        value = v;
    }
    
    public String getKey()
    { 
        return key;
    }
    
    public String getValue()
    { 
        return value;
    }

    public int compareTo(Item otherObject)
    {
        Item other = (Item) otherObject;
        return key.compareTo(other.key);
    }

    private String key;
    private String value;
}

修复说明 #

1. 改用in.nextLine()读取姓名，确保获取到完整的一行输入，和文件中存储的姓名格式完全匹配。
2. 在读取号码后调用一次in.nextLine()，消耗掉输入缓冲区中残留的换行符，避免影响后续姓名的读取。
3. 增加索引合法性判断，避免因查找失败（返回负索引）调用get(index)抛出IndexOutOfBoundsException异常。

内容的提问来源于stack exchange，提问作者Cab