使用Arrays.binarySearch时数组未返回正确结果问题求助

Hey Tyler, let's break down why your binary search isn't working right and fix it up!

The Core Issue #

Arrays.binarySearch() relies on the binary search algorithm, which has a non-negotiable requirement: the array you're searching must be sorted in ascending order (using the natural ordering of the elements, like dictionary order for Strings).

Looking at your code, you're collecting user IDs directly into the userID array without sorting it first. When you run binarySearch on an unsorted array, the algorithm can't properly narrow down the search range—this leads to incorrect indices or negative values even when the user ID exists in the array.

Another Hidden Pitfall #

Even if you sorted the userID array directly, you'd run into a second problem: the password array would no longer align with the sorted user IDs. You need to keep each user ID paired with its corresponding password through the sorting step.

Fixes & Modified Code #

Let's go over two solid solutions, starting with the cleanest approach.

Solution 1: Use a Custom Class to Pair IDs and Passwords #

Create a class to hold each user's credentials, implement Comparable so we can sort the array, then run the binary search on the sorted array.

import java.util.*; 

class UserCredential implements Comparable<UserCredential> {
    private String userId;
    private String password;

    public UserCredential(String userId, String password) {
        this.userId = userId;
        this.password = password;
    }

    public String getUserId() {
        return userId;
    }

    public String getPassword() {
        return password;
    }

    // Define natural ordering by user ID (dictionary order)
    @Override
    public int compareTo(UserCredential other) {
        return this.userId.compareTo(other.userId);
    }
}

//@Author: Tyler Cage 
public class Main { 
    public static void main(String[] args) { 
        Scanner scnr = new Scanner(System.in); 
        UserCredential[] credentials = new UserCredential[3]; 

        // Collect user credentials
        for (int i = 0; i < credentials.length; i++){ 
            System.out.print("User id at index #" + i + " "); 
            String id = scnr.next(); 
            System.out.print("Password at index #" + i + " "); 
            String pwd = scnr.next(); 
            credentials[i] = new UserCredential(id, pwd); 
        } 

        // Sort the array BEFORE binary search
        Arrays.sort(credentials);

        // Get user input for search
        System.out.print("Enter user id: "); 
        String userIdInput = scnr.next(); 

        // Perform binary search
        int index = Arrays.binarySearch(credentials, new UserCredential(userIdInput, ""));

        // Handle the result
        if (index >= 0) {
            System.out.println("Found user! Password: " + credentials[index].getPassword());
        } else {
            System.out.println("User not found.");
        }

        scnr.close();
    } 
}

Solution 2: Preserve Index Mapping (No Custom Class) #

If you prefer not to create a new class, you can map each user ID to its original index, sort those mappings, then rebuild aligned sorted arrays for IDs and passwords:

import java.util.*; 
import java.util.AbstractMap.SimpleEntry;

//@Author: Tyler Cage 
public class Main { 
    public static void main(String[] args) { 
        Scanner scnr = new Scanner(System.in); 
        String[] userID = new String[3]; 
        String[] password = new String[3]; 

        // Collect input
        for (int i = 0; i < userID.length; i++){ 
            System.out.print("User id at index #" + i + " "); 
            userID[i] = scnr.next(); 
            System.out.print("Password at index #" + i + " "); 
            password[i] = scnr.next(); 
        } 

        // Map user IDs to their original indices
        List<SimpleEntry<String, Integer>> idIndexPairs = new ArrayList<>();
        for (int i = 0; i < userID.length; i++) {
            idIndexPairs.add(new SimpleEntry<>(userID[i], i));
        }

        // Sort the pairs by user ID
        Collections.sort(idIndexPairs, Map.Entry.comparingByKey());

        // Build sorted arrays with aligned IDs and passwords
        String[] sortedUserID = new String[3];
        String[] sortedPassword = new String[3];
        for (int i = 0; i < idIndexPairs.size(); i++) {
            sortedUserID[i] = idIndexPairs.get(i).getKey();
            sortedPassword[i] = password[idIndexPairs.get(i).getValue()];
        }

        // Search
        System.out.print("Enter user id: "); 
        String userIdInput = scnr.next(); 
        int index = Arrays.binarySearch(sortedUserID, userIdInput);

        // Handle result
        if (index >= 0) {
            System.out.println("Found user! Password: " + sortedPassword[index]);
        } else {
            System.out.println("User not found.");
        }

        scnr.close();
    } 
}

Key Notes to Remember #

• Always sort the array before calling Arrays.binarySearch().
• When working with paired data (like IDs and passwords), never sort one array without updating the other to maintain alignment.
• Arrays.binarySearch() returns a negative value if the element isn't found: specifically -(insertion point) - 1—so always check if the result is >= 0 to confirm a match.

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