如何使用ListIterator对List集合执行递归二进制搜索？

Question

我想使用ListIterator实现递归二进制搜索功能，以在每个递归步骤遍历列表。到目前为止，我有

import java.util.ListIterator;
import java.lang.Comparable;
import java.util.List;

public class BinarySearch<E extends Comparable<E>> {

    List<E> arr;
    ListIterator<E> iter;
    E target;

    public BinarySearch(List<E> arr, E target) {
        this.arr = arr;
        this.target = target;
        iter = arr.listIterator();
    }

    public int search() {
        return binarySearch();
    }

    private int binarySearch(int l, int h) {
        if(l > h) return -1;

        int mid = l + (h - l) / 2;
    }
}

我如何在每个递归步骤中使用ListIterator来执行二进制searhc，因此每次将其移至中间元素？

Answer 1

在执行搜索之前先排序列表，然后再执行搜索，如下所示：

    static class BinarySearch<E extends Comparable<E>> {

        List<E> list;
        E target;

        public BinarySearch(List<E> list, E target) {
            this.list = list;
            this.target = target;
            Collections.sort(list);
        }

        public int search() {
            return binarySearch(0, list.size() - 1);
        }

        private int binarySearch(int lo, int hi) {
            if (lo > hi || hi < 0)
                return -1;

            int mid = lo + (hi - lo) / 2;
            int cmp = list.get(mid).compareTo(target);
            if (cmp > 0)
                return binarySearch(lo, mid - 1);
            else if (cmp < 0)
                return binarySearch(mid + 1, hi);
            else
                return mid;
        }
    }