題目 1711:
數(shù)據(jù)結(jié)構(gòu)-有序表的折半查找
時(shí)間限制: 2s
內(nèi)存限制: 96MB 提交: 4357 解決: 2956
題目描述
用有序表表示靜態(tài)查找表時(shí)，通常檢索函數(shù)可以用折半查找來實(shí)現(xiàn)。
折半查找的查找過程是：首先確定待查記錄所在的范圍，然后逐步縮小范圍直到找到或者確定找不到相應(yīng)的記錄為止。而每次需要縮小的范圍均為上一次的一半，這樣的查找過程可以被稱為折半查找。
其查找過程可以描述如下：
在本題中，讀入一串有序的整數(shù)，另外給定多次查詢，判斷每一次查詢是否找到了相應(yīng)的整數(shù)，如果找到則輸出整數(shù)相應(yīng)的位置。
輸入格式
輸入的第一行包含2個(gè)正整數(shù)n和k，分別表示共有n個(gè)整數(shù)和k次查詢。其中n不超過1000，k同樣不超過1000。
第二行包含n個(gè)用空格隔開的正整數(shù)，表示n個(gè)有序的整數(shù)。輸入保證這n個(gè)整數(shù)是從小到大遞增的。
第三行包含k個(gè)用空格隔開的正整數(shù)，表示k次查詢的目標(biāo)。
輸出格式
只有1行，包含k個(gè)整數(shù)，分別表示每一次的查詢結(jié)果。如果在查詢中找到了對應(yīng)的整數(shù)，則輸出其相應(yīng)的位置，否則輸出-1。
請?jiān)诿總€(gè)整數(shù)后輸出一個(gè)空格，并請注意行尾輸出換行。
樣例輸入
8 3 1 3 5 7 8 9 10 15 9 2 5
樣例輸出
5 -1 2
提示
零基礎(chǔ)同學(xué)可以先學(xué)習(xí)視頻課程，包含C/C++、Python、百練、藍(lán)橋杯輔導(dǎo)、算法數(shù)據(jù)結(jié)構(gòu)等課程，提供視頻講解以及配套習(xí)題，還有老師答疑，點(diǎn)擊這里了解課程詳情