1

我正在尝试创建一种方法，该方法以二进制形式插入然后对元素进行排序。

我遇到的问题是我的代码没有正确插入数据，这意味着输出似乎根本没有顺序。

该列表没有组织，数据按插入的顺序添加。

现在，有两个问题，我在这里做错了什么？以及如何解决这个问题？

public void insertBinarySearch(long value) // put element into array
{       
    int j = 0;
    int lower = 0;
    int upper = elems-1;
    int cur = 0;

    while (cur < elems)
    {
        cur = (lower + upper ) / 2;

        if(a[cur] < value)
        {
            j = cur + 1;
            break;
        }
        else if(a[cur] > value)
        {
            j = cur;
            break;
        }
        else
        {
            if(a[cur] < value)
                lower = cur + 1;
            else
                upper = cur - 1;
        }
    }

    for(int k = elems; k > j; k--)
        a[k] = a[k-1];

    a[j] = value;

    elems++;
}
4

3 回答 3

3 
while (lower <= upper)
{
    curIn = (lower + upper ) / 2;

        if(a[curIn] < value)
            lower = cur + 1;
        else if(a[curIn] > value)
            upper = cur - 1;
        else if (a[curIn] == value)
            break;
}
if(a[curIn] <= value)
    j = curIn + 1;
else j = curIn;

应该管用。

于 2012-09-30T03:25:09.667 回答
1

伙计，你几乎明白了，只需调试代码并找到一些缺失的语句（if's）。如果你发现那些缺失的语句，你的代码看起来比我的好。别看我的，你就在那里，很近。

让我知道任何错误和差异等。快乐编码！

public class Insertion {
    private int[] a;
    int n;
    int c;

    public Insertion()
    {
        a = new int[10];
        n=0;
    }

    int find(int key)
    {
        int lowerbound = 0;
        int upperbound = n-1;

        while(true)
        {
            c = (lowerbound + upperbound)/2;
            if(n==0)
                return 0;
            if(lowerbound>=upperbound)
            {
                if(a[c]<key)
                    return c++;
                else
                    return c;
            }
            if(a[c]>key && a[c-1]<key)
                return c;
            else if (a[c]<key && a[c+1]>key)
                return c++;
            else
            {
                if(a[c]>key)
                    upperbound = c-1;
                else
                    lowerbound = c+1;
            }
        }
    }

    void insert(int key)
    {
       find(key);
       for(int k=n;k>c;k--)
       {
           a[k]=a[k-1];
       }
       a[c]=key;
       n++;
    }
    void display()
    {
        for(int i=0;i<10;i++)
        {
            System.out.println(a[i]);
        }
    }

    public static void main(String[] args)
    {
        Insertion i=new Insertion();
        i.insert(56);
        i.insert(1);
        i.insert(78);
        i.insert(3);
        i.insert(4);
        i.insert(200);
        i.insert(6);
        i.insert(7);
        i.insert(1000);
        i.insert(9);
        i.display();
    }
}
于 2015-04-12T01:15:30.347 回答
0

如果您尝试将一个项目插入到未排序的列表中，那么如果您之后不直接对其进行排序，您就不能期望该列表会被排序。

二进制搜索只能用于排序列表。您的结果没有其他意义：毕竟，如果您正在搜索一个元素 - 例如让我们使用 8 - 您如何知道一个项目是否属于 8 之前或之后？

[ 1 2 3 4 5 6 7 8 9 10 11 ]

请注意，如果我找到 8，我知道它之后的所有内容都大于 8，而之前的所有内容都小于 8。但是这个列表呢？

[ 1 4 11 9 8 6 7 2 5 3 10 ]

哎呀！现在，看 8，你可以看到 8 的位置不再与小于或大于 8 的项目有任何关系。试图在这个列表中用二分搜索找到一个元素会给你错误的信息，是否它会找到您正在寻找的项目。

要使其正常工作，请确保列表始终排序（如果您始终将项目插入列表中的正确位置，则应该是这种情况），或者在插入新元素之前对其进行排序。二进制搜索将为您服务就好了。

于 2012-09-30T03:32:57.537 回答