public class sorted { public static int binarySearch(int[] data, int target) {
int start = 0;
int end = data.length - 1;
while(start <= end) {
int mid = (start + end )/2;
if(target< data[mid]) {
end = mid -1;
}else if(target > data[mid]) {
start = mid +1;
}else {
return mid;
}
}
return -1;
}
public static void main(String[] args) {
int[] values = {1,2,3,4,5,8,8,8,};
int target = 8;
int a = binarySearch( values,target);
System.out.println(a);
}}
4 回答
米脂
TA貢獻(xiàn)1836條經(jīng)驗(yàn) 獲得超3個(gè)贊
這就是返回5啊，不然要返回什么……
5是指target的引索值，英文叫index。程序里value為1,2,3,4,5,8,8,8 它的引索值是 0，1，2，3，4，5，6，7，8.
你的這段程序就是用二分法在value里面找target，輸出target的引索值。由于target=8，所以找到了第一個(gè)8，他的引索是5，所以輸出5.
仔細(xì)看看，可以帶值進(jìn)去看。
剛開始start=0， end=8-1=7. 由于start小于end，所以執(zhí)行循環(huán)，mid=（0+7）/2=3，因?yàn)閙id是int型，所以只保留整數(shù)部分。
那么data[3]應(yīng)該就是value里面第4個(gè)數(shù)，也就是4。那么4<8,所以start=mid+1=3+1=4. 第一次循環(huán)結(jié)束，由于start4<end7，所以再次進(jìn)入循環(huán)
這時(shí)mid=（4+7）/2=5，只保留整數(shù)部分。那么data[5]就是value里第六個(gè)數(shù)，也就是8. 因?yàn)閐ata[5]8=target8, 所以進(jìn)入elise后面的語句。就是return mid。
這不就return了5了嗎。
慕容708150
TA貢獻(xiàn)1831條經(jīng)驗(yàn) 獲得超4個(gè)贊
額，這個(gè)是折半查找，查8，對吧。
一開始和中間第4的值開始比較，也就是8 和 data[3] ， 8 > 4
start=mid+1=4，再進(jìn)行比較，這時(shí)候mid=(4+7)/2=5,也就是8和data[5]比較, 8 = 8，return mid，這個(gè)時(shí)候mid=5
慕俠2389804
TA貢獻(xiàn)1719條經(jīng)驗(yàn) 獲得超6個(gè)贊
第一遍查找，mid值為3，進(jìn)入else if(target > data[mid]) { start = mid +1;}這一句，start變?yōu)?；
第二遍查找，mid值為5，進(jìn)入else { return mid;} 這一句，不就是5了么
}
泛舟湖上清波郎朗
TA貢獻(xiàn)1818條經(jīng)驗(yàn) 獲得超3個(gè)贊
這是二分查找,二分查找法就是查詢數(shù)組中指定值在數(shù)組中第一次出現(xiàn)的索引(前提數(shù)組必須是有序的).
你的代碼里
start:數(shù)組的開始索引
end:數(shù)組的最大索引
如果開始索引小于最大索引,就執(zhí)行查找,先將開始索引和結(jié)束索引做除法,求得中間索引,然后判斷中間索引對應(yīng)的值和你要找的目標(biāo)值的大小關(guān)系:
當(dāng)中間索引的值>目標(biāo)值,start = 0,end = min - 1 繼續(xù)循環(huán)在中間索引的右邊繼續(xù)找
當(dāng)中間索引的值<目標(biāo)值,start = min + 1,end = data.length-1 繼續(xù)循環(huán)在中間索引的左邊繼續(xù)找
當(dāng)中間索引的值=目標(biāo)值, 中間索引就是你要找的值,返回mid就可以了
也可以直接調(diào)用Arrays的二分查找法
添加回答
舉報(bào)
0/150
提交
取消