有序字符串集合算法实现求助：需用get方法且不可修改指定类

Hey there! Let's walk through this clearly—since you're working with an ordered string collection, restricted to using the get method, and have unmodifiable test/utility classes, binary search is your best bet here. It’s efficient, relies entirely on index-based element access (perfect for get), and is a standard algorithm you can reference easily.

Step 1: Understand the Core Problem & Tool #

Since your collection is ordered lexicographically, binary search is ideal. It works by repeatedly dividing the search range in half, using get to fetch the middle element, and comparing it to your target string. No extra methods needed—just get and basic string comparison.

Step 2: Implement the Search Logic #

Assuming you need to write a Search class (paired with the unmodifiable SearchTest you shared), here’s a concrete Java implementation that sticks to your rules:

First, the Search class (this is what you’ll write):

public class Search {
    // Find the index of a target string in an ordered collection, using only get()
    public static int findTarget(SortedStringCollection collection, String target) {
        int left = 0;
        int right = collection.size() - 1;

        // Handle empty collection case upfront
        if (collection.size() == 0) {
            return -1;
        }

        while (left <= right) {
            // Calculate mid index safely (avoids integer overflow)
            int midIndex = left + (right - left) / 2;
            String midString = collection.get(midIndex);
            int comparison = midString.compareTo(target);

            if (comparison == 0) {
                // Target found—return its index
                return midIndex;
            } else if (comparison < 0) {
                // Mid string is smaller than target: search right half
                left = midIndex + 1;
            } else {
                // Mid string is larger than target: search left half
                right = midIndex - 1;
            }
        }

        // Target not present in the collection
        return -1;
    }
}

Step 3: Test with Your Unmodifiable SearchTest Class #

Your SearchTest can call this method to validate functionality. For example, if your test class looks like this (building on the partial code you shared):

import java.io.IOException;

public class SearchTest {
    /**
     * Test program for the Search class.
     * Put whatever tests you like in the body of the method.
     * @param args the command line arguments
     * @throws java.io.IOException of error reading the input
     */
    public static void main(String[] args) throws IOException {
        // Example: Create a pre-populated ordered string collection
        // (Assuming SortedStringCollection is your unmodifiable collection class)
        SortedStringCollection testSet = new SortedStringCollection(
            new String[]{"apple", "banana", "cherry", "date", "elderberry"}
        );

        // Test 1: Find an existing string
        int foundIndex = Search.findTarget(testSet, "cherry");
        System.out.println("Found 'cherry' at index: " + foundIndex); // Should print 2

        // Test 2: Find a non-existent string
        int notFoundIndex = Search.findTarget(testSet, "fig");
        System.out.println("Found 'fig' at index: " + notFoundIndex); // Should print -1
    }
}

Key Notes to Remember #

• Use compareTo for Strings: Since the collection is ordered, String.compareTo() gives you the correct lexicographic comparison (negative = mid < target, positive = mid > target, zero = match).
• Safe Index Calculation: left + (right - left)/2 prevents integer overflow, which can happen with (left + right)/2 if your collection is large.
• Edge Cases: We handle empty collections upfront, and the loop naturally handles single-element collections too.

This implementation fits your requirements perfectly—no fancy methods, just strict use of get to access elements, and it leverages the ordered nature of your collection for efficiency.

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