二分插入算法,请帮我看看我的代码错在那里?我已经走进死胡同了,脑子糊涂了.好几天想不通!

Question

在看<<Java数据结构与算法(第二版)>>,做第2章的习题,要求做一个二分查找的插入算法(针对数组的）,做了好几天脑子有点乱,怎么也跳不出圈子，找不到问题的关键。希望那位大侠好好点醒我，思想出错在那里谢谢
代码如下:
public void insert (long value)
    {
        /**
         * 假设用户输入的值没有重复（为了减少算法复杂度）。
         * 输入示例：
         * arr.insert(77);
         * arr.insert(99);
         * arr.insert(44);
         * arr.insert(55);
         * arr.insert(22);
         * arr.insert(88);
         * arr.insert(11);
         * arr.insert(00);
         * arr.insert(66);
         * arr.insert(33);
         * 输出结果：0 11 33 22 55 88 66 44 99 77 
         */
        int lowerBound = 0;
        int upperBound = nElems - 1;
        int curIn = lowerBound;
       
        while (true)
        {
            curIn = (lowerBound + upperBound) / 2;
            if(lowerBound > upperBound)
                break;
            if(a[curIn] < value)
                lowerBound = curIn + 1;
            else
                upperBound = curIn - 1;
        }
        
        for(int k=nElems; k>curIn; k--)
            a[k] = a[k - 1];
        
        a[curIn] = value;
        nElems++;
    }

Answer 1

你写的while循环永远都是真的 那么找到了最后他还会继续执行while里面的语句

Answer 2

正解，要不楼主用do ...while 试试

Answer 3

while (true) 
        { 
            curIn = (lowerBound + upperBound) / 2; 
            /*if(a[curIn]==你要查的那个数）
              break;
            if(lowerBound > upperBound) 
                break; 
            if(a[curIn] < value) 
                lowerBound = curIn + 1; 
            else 
                upperBound = curIn - 1; 
        } 
        
        for(int k=nElems; k>curIn; k--) 
            a[k] = a[k - 1];
        
        a[curIn] = value; 
        nElems++; 
    }

Answer 4

while (true) 
        { 
            curIn = (lowerBound + upperBound) / 2; 
            /*if(a[curIn]==你要查的那个数）
              break;*/
            if(lowerBound > upperBound) 
                break; 
            if(a[curIn] < value) 
                lowerBound = curIn + 1; 
            else 
                upperBound = curIn - 1; 
        } 
        
        for(int k=nElems; k>curIn; k--) 
            a[k] = a[k - 1];
        
        a[curIn] = value; 
        nElems++; 
    }

Answer 5

while (true) 
        { 
            curIn = (lowerBound + upperBound) / 2; 
            /*if(a[curIn]==你要查的那个数）
              break;*/
            if(lowerBound > upperBound) 
                break; 
            if(a[curIn] < value) 
                lowerBound = curIn + 1; 
            else 
                upperBound = curIn - 1; 
        } 
        
        for(int k=nElems; k>curIn; k--) 
            a[k] = a[k - 1];
        
        a[curIn] = value; 
        nElems++; 
    }

Answer 6

首先感谢大家的回复.再下有几点说明:1.这个算法假设用户输入的值没有重复（为了减少算法复杂度）,所以只找插入到当前值的合适位置.
if(a[curIn]==你要查的那个数）
  break;
这一句永远不会发生。2.你写的while循环永远都是真的 那么找到了最后他还会继续执行while里面的语句回复:
if(lowerBound > upperBound) 
  break; 
这一句是辟免死循环的关键，lowerBound > upperBound时，条件不存在退循环。lowerBound = upperBound时，则只有一个元素，所以还得再循环一次。3.数组要先排序啊.不排序二分查找法没有意义
回复：没办法啊，书中试验题就是这样要求的。只要求在插入时使用“二分查找”找到合适插入位置，然后再插入新值（同时为新值搬移出位置）。再次感谢大家，还有请大侠们帮忙

Answer 7

没看清 原来是不是查找
你要的是插入啊  不好意思
二分查找法的前提好象是要有序排列如何用来插入就不知道了难道是查找a[i]<要插入的数<a[i+1]  这个位置？

Answer 8

这些人啊，没点水也在这乱说....不会就顶就是了，678楼在那里把LZ的代码再粘一遍有什么意思啊？
假设你的nElems，和a[]数组是全局变量，当然你在java类里有可能是成员变量，总之假设这些个东西没问题。 
尤其是nElems，请提前初始化为0；
然后，把这句改过来就可以了 
a[curIn] = value; 
改为： 
a[lowerBound] = value;

Answer 9

代码没有错啊，我做了一个程序运行正常的
这个方法是在一个数组中插入数据，如果所有的数据都是通过这个方法插入的话，这个数组一定是有序的。
二分法仅仅是用来快速定位需要插入的位置import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class insertarray {
static final int MAX_NUM = 50;
long [] a = new long[MAX_NUM];
int nElems;

public static void main(String [] args) throws IOException
{
int i,num;
insertarray arr = new insertarray();

BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

for(i=0;i<MAX_NUM;i++){
System.out.println("input "+i +"num");
num=Integer.parseInt(in.readLine());
if (num ==-1) break;
arr.insert(num);
}
arr.print();

}

public void print()
{
System.out.println("Array Content:");
for(int i= 0;i<nElems;i++)
System.out.print(a[i]+" ");

}

public void insert(long value) 
    { 
        /** 
        * 假设用户输入的值没有重复（为了减少算法复杂度）。 
        * 输入示例： 
        * arr.insert(77); 
        * arr.insert(99); 
        * arr.insert(44); 
        * arr.insert(55); 
        * arr.insert(22); 
        * arr.insert(88); 
        * arr.insert(11); 
        * arr.insert(00); 
        * arr.insert(66); 
        * arr.insert(33); 
        * 输出结果：0 11 33 22 55 88 66 44 99 77 
        */ 
        int lowerBound = 0; 
        int upperBound = nElems - 1; 
        int curIn = lowerBound; 
      
        //这个循环查找插入的位置，使用的是二分法
        while (true) 
        { 
            curIn = (lowerBound + upperBound) / 2; 
            if(lowerBound > upperBound) 
                break; 
            if(a[curIn] < value) 
                lowerBound = curIn + 1; 
            else 
                upperBound = curIn - 1; 
        } 
        
        //将这个位置之后的所有元素向后移动，腾出空间
        for(int k=nElems; k>curIn; k--) 
            a[k] = a[k - 1];         //保存新增的数据
        a[curIn] = value; 
        nElems++; 
    }}

Answer 10

while (true) 
        { 
            curIn = (lowerBound + upperBound) / 2; 
            /*if(a[curIn]==你要查的那个数）
              break;*/
            if(lowerBound > upperBound) 
                break; 
            if(a[curIn] < value) 
                lowerBound = curIn + 1; 
            else 
                upperBound = curIn - 1; 
        } 
        
        for(int k=nElems; k>curIn; k--) 
            a[k] = a[k - 1];
        
        a[curIn] = value; 
        nElems++; 
    }

Answer 11

首先表示感谢。
"为了减少算法复杂度”这句话只针对上述我给出的代码。为了减少在插入时增加，检查数组中的数据项是否与用户输入的值有重复。关于java中数组初始化的问题说明：
当创建整型数组之后，如果不另行指定，那么整型数组会自动初始化为空（整型是0)。与C++不同的是，即使通过方法（函数）来定义数组也是这样的。针对上述算法中，也就是说数组一但创建它即是有序的（所有数据项都是0）。所以使用“二分查找”的条件已经成熟。习题要求我用“二分查找”找到插入值的合适位置，当所有值被插入完后，整个数组中的数据项应该是按a[i] <要插入的数 <a[i+1] 排序的。

Answer 12

首先表示感谢,通过你给出的代码修改后,整个算法运行正常,并且已经达到了上述要求("二分查找"合适位置,并且插入后整个数组中的数据项按升序排列)..请你再次点解我一下,我的想法错在那里.我本以为curIn是合适的位置,为何合适的位置是lowerBound呢???我糊涂啊。

Answer 13

算法逻辑不容易错，事实上也没错，是你插入位置少算了 计算机整数除法要与数学除法区别开
比如楼主程序第二步就插倒了 改为：curIn = (lowerBound + upperBound + 1 )/ 2;

Answer 14

这里的break是循环唯一的出口 
因此可以这样看循环体： 
if(a[curIn] < value) 
                lowerBound = curIn + 1; 
            else 
                upperBound = curIn - 1; 
curIn = (lowerBound + upperBound) / 2; 
            if(lowerBound > upperBound) 
                break; 从break出去以后lowerBound 指向的位置正是前一次循环 
if(a[curIn] < value) 
    lowerBound = curIn + 1; 进行移动后的位置，这个位置就是比value小的最后一个数后面的位置了嘛 
那么value自然排在这里了 ,curIn此时还指向比value小的最后一个数呢！
总体来说，curIn在算法中只是作为一个curIn = (lowerBound + upperBound) / 2; 形式的均值杠杆在用...