|
下面是折半查找的實(shí)現(xiàn)，data是按升序排列的數(shù)據(jù)，x是查找下標(biāo)，y是查找的上標(biāo)， v是查找的數(shù)值，返回v在data的索引，若沒(méi)找到返回-1。代碼不正確是____。 public int bsearch(int[] data, int x, int y, int v) { int m; while(x<y){ //1 m = x + (y-x)/2; //2 if(data[m] == v) return m; //3 else if(data[m] > v) y = m; //4 else x = m; //5 } return -1; //6 } 正確的方法： 上下標(biāo)沒(méi)有寫(xiě)清楚，題目所指的應(yīng)該是[x,y),這樣5應(yīng)該是m-1 而在下標(biāo)為[x,y]的情況下，1,4,5都是有問(wèn)題的。。。。正確版本應(yīng)該是這樣吧 while(x<=y) { m = x + (y-x)/2; //2 if(data[m] == v) return m; //3 else if(data[m] > v) y = m-1; //4 else x = m+1; //5 } 補(bǔ)充：這里下標(biāo)是個(gè)坑，記住上限有沒(méi)有包含就可以對(duì)付1,4,5處的問(wèn)題（熟記理解兩個(gè)版本的代碼區(qū)別），然后是2，寫(xiě)成x+(y-x)/2是防止xy都很大的情況下x+y越界。這樣的話應(yīng)對(duì)二分查找應(yīng)該夠了 |
|
|
來(lái)自： 雪柳花明 > 《C 筆試 理論基礎(chǔ)題 準(zhǔn)備》
