使用两种不同的算法搜索排序列表以查找是否存在满足 X[i]=i 的索引 i

Question

请注意，该列表绝不会包含重复项。

列表是从文本文件加载的，如下1,2,3,4,5,6,7,8,9。

列表排序后我的第一个选择是线性搜索并且工作正常。然后我尝试使用二进制搜索，但它不能正常工作。

代码如下：

public boolean binarySearch() {

        int i=0;
        int size = list.size() - 1;

        while (i <= size) {

            int mid = (i + size) / 2;
            if (mid == list.get(mid)) {
                return true;
            }
            if (mid < list.get(mid)) {
                size = mid - 1;
            } else {
                i = mid + 1;
            }
        }
        return false;
    }

Answer 1

这是一个O(log n)解决方案。

public static void main(String args[]) {
    System.out.println(binarySearch(new int[] {-100, -50, -30, 3, 500, 800}));
    System.out.println(binarySearch(new int[] {-100, -50, -30, 42, 500, 800}));
    System.out.println(binarySearch(new int[] {-8, 1, 2, 3, 4, 100, 200, 300, 500, 700, 9000}));
}

// Searches for a solution to x[i]=i, returning -1 if no solutions exist.
// The algorithm only works if the array is in ascending order and has no repeats.
// If there is more than one solution there is no guarantee which will
// be returned. Worst case time complexity O(log n) where n is length of array.
public static int binarySearch(int[] x) {
    if (x == null || x.length == 0)
        return -1;
    int low = 0;
    if (x[low] == low)
        return 0;
    else if (x[low] > low)
        return -1;
    int high = x.length - 1;
    if (x[high] == high)
        return high;
    else if (x[high] < high)
        return -1;
    while (high - low >= 2) {
        int mid = (high + low) / 2;
        if (x[mid] == mid)
            return mid;
        else if (x[mid] > mid)
            high = mid;
        else low = mid;
    }
    return -1;
}

Answer 2

public class NewMain1 {

public static void main(String[] args) {
    int [] x = {1,2,3,4,5,6};
    int value = 7;
    boolean check = binarySearch(x,value);
    System.out.println(check);
}
public static boolean binarySearch(int [] list , int value) {

    int i=0;
    int size = list.length - 1;

    while (i <= size) {

        int mid = (i + size) / 2;
        if (value == list[mid]) {
            return true;
        }
        if (value < list[mid]) {
            size = mid - 1;
        } else {
            i = mid + 1;
        }
    }
    return false;
}

我想这对你有帮助

使用两种不同的算法搜索排序列表以查找是否存在满足 X[i]=i 的索引 i

Searching a sorted list with two different algorithms to find if there exists an index i such that X[i]=i

java

algorithm

binary-search

sortedlist