修改二进制搜索算法，使其即使在未排序的列表上也能工作。

Question

修改二进制搜索算法，使其即使在未排序的列表上也能工作。最好在主菜单中创建一个新选项（案例 6），以便保留原来的二进制搜索。除了一些逻辑变化外，新的二分搜索方法应该与之前的方法具有非常相似的结构。

这是我的原始代码：

// *****************************************************************
// IntegerListB.java
//
// Defines an IntegerList class with methods to create, fill,
// sort, and search in a list of integers. (Version B - for use
// in the binary search lab exercise)
//
// *****************************************************************
public class IntegerListB
{
    int[] list; //values in the list
    // ------------------------------------
    // Creates a list of the given size
    // ------------------------------------
    public IntegerListB (int size)
    {
        list = new int[size];
    }
    // -------------------------------------------------------------
    // Fills the array with integers between 1 and 100, inclusive
    // -------------------------------------------------------------
    public void randomize()
    {
        for (int i=0; i<list.length; i++)
            list[i] = (int)(Math.random() * 100) + 1;
    }
    // ----------------------------------------
    // Prints array elements with indices
    // ----------------------------------------
    public void print()
    {
        for (int i=0; i<list.length; i++)
            System.out.println(i + ":\t" + list[i]);
    }
    // ------------------------------------------------------------------
    // Returns the index of the first occurrence of target in the list.
    // Returns -1 if target does not appear in the list.
    // ------------------------------------------------------------------
    public int linearSearch(int target)
    {
        int location = -1;
        for (int i=0; i<list.length && location == -1; i++)
            if (list[i] == target)
                location = i;
        return location;
    }
    //-----------------------------------------------------------------
    //Returns the index of an occurrence of target in the list, -1
    //if target does not appear in the list.
    //-----------------------------------------------------------------
    public int binarySearchRec(int target)
    {
        return binarySearchR (target, 0, list.length-1);
    }
    //-----------------------------------------------------------------
    //Recursive implementation of the binary search algorithm.
    //If the list is sorted the index of an occurrence of the
    //target is returned (or -1 if the target is not in the list).
    //-----------------------------------------------------------------
    private int binarySearchR (int target, int lo, int hi)
    {
        int index;
        if ( hi < lo) // fill in the "not found" condition
            index = -1;
        else
        {
            int mid = (lo + hi)/2;
            if ( list[mid] == target) // found it!
                index = mid;
            else if (target < list[mid])
                // fill in the recursive call to search the first half
                // of the list
                index = binarySearchR(target, lo, mid-1);
            else
                // search the last half of the list
                index = binarySearchR(target, mid+1, hi);
        }
        return index;
    }

    //------------------------------------------------------------------
    //Sorts the list into ascending order using the selection sort algorithm.
    //------------------------------------------------------------------
    public void selectionSort()
    {
        int minIndex;
        for (int i=0; i < list.length-1; i++)
        {
            //find smallest element in list starting at location i
            minIndex = i;
            for (int j = i+1; j < list.length; j++)
                if (list[j] < list[minIndex])
                    minIndex = j;
            //swap list[i] with smallest element
            int temp = list[i];
            list[i] = list[minIndex];
            list[minIndex] = temp;
        }
    }

这是driver class:

// ***************************************************************
// IntegerListBTest.java
//
// Provides a menu-driven tester for the IntegerList class.
// (Version B - for use with the binary search lab exerice)
//
// ***************************************************************
import java.util.Scanner;
public class IntegerListBTest
{
    static IntegerListB list = new IntegerListB (10);
    static Scanner scan = new Scanner(System.in);
    // ----------------------------------------------------------------
    // Create a list, then repeatedly print the menu and do what the
    // user asks until they quit.
    // ----------------------------------------------------------------
    public static void main(String[] args)
    {
        printMenu();
        int choice = scan.nextInt();
        while (choice != 0)
        {
            dispatch(choice);
            printMenu();
            choice = scan.nextInt();
        }
    }
    // ---------------------------------------------------
    // Does what the menu item calls for.
    // ---------------------------------------------------
    public static void dispatch(int choice)
    {
        int loc;
        switch(choice)
        {
        case 0:
            System.out.println("Bye!");
            break;
        case 1:
            System.out.println("How big should the list be?");
            int size = scan.nextInt();
            list = new IntegerListB(size);
            list.randomize();
            break;
        case 2:
            list.selectionSort();
            //invoke the sorting method in the IntegerListB class
            break;
        case 3:
            System.out.print("Enter the value to look for: ");
            loc = list.linearSearch(scan.nextInt());
            if (loc != -1)
                System.out.println("Found at location " + loc);
            else
                System.out.println("Not in list");
            break;
        case 4:
            System.out.print("Enter the value to look for: ");
            loc = list.binarySearchRec(scan.nextInt());
            if (loc != -1)
                System.out.println("Found at location " + loc);
            else
                System.out.println("Not in list");
            break;
        case 5:
            list.print();
            break;      
        default:
            System.out.println("Sorry, invalid choice");
        }
    }
    // ----------------------------
    // Prints the user's choices.
    // ----------------------------
    public static void printMenu()
    {
        System.out.println("\n Menu ");
        System.out.println(" ====");
        System.out.println("0: Quit");
        System.out.println("1: Create new list elements (** do this first!! **)");
        System.out.println("2: Sort the list using selection sort");
        System.out.println("3: Find an element in the list using linear search");
        System.out.println("4: Find an element in the list using binary search");
        System.out.println("5: Print the list");
        System.out.println("6: Find an element in the unsorted list using binary search");
        System.out.print("\nEnter your choice: ");  
    }
}

Answer 1

二分查找需要按定义对元素进行排序。

"In computer science, a binary search or half-interval search algorithm finds the position of a specified input value (the search "key") 在按键值排序的数组中。"

http://en.wikipedia.org/wiki/Binary_search_algorithm