我想找到一個(gè)目標(biāo)值 4 在序列 [1, 1, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 6] 中首先出現(xiàn)的位置。當(dāng)我使用 java.util.Arrays.binaySearch 時(shí)，它返回索引是 9，但我期望的是 7。我看java.util.Arrays.binaySearch我發(fā)現(xiàn)了一些評(píng)論：如果數(shù)組包含多個(gè)具有指定值的元素，則無(wú)法保證找到哪一個(gè)。那么如何在Java中實(shí)現(xiàn)一個(gè)lower_bound二分查找算法，返回目標(biāo)值就首先出現(xiàn)了。注意：lower_bound概念來(lái)自C++，但我不太了解C++。
3 回答
當(dāng)年話下
TA貢獻(xiàn)1890條經(jīng)驗(yàn) 獲得超9個(gè)贊
我認(rèn)為下面的實(shí)現(xiàn)將正確完成工作：
int firstOccurrence(int[] sequence, int x) {
int min = 0;
int max = sequence.length - 1;
int result = -1;
while (min <= max)
{
// find the mid value and compare it with x
int mid = min + ((max - min) / 2);
// if x is found, update result and search towards left
if (x == sequence[mid]) {
result = mid;
max = mid - 1;
} else if (x < sequence[mid]) {
// discard right half
max = mid - 1;
} else {
// discard left half
min = mid + 1;
}
}
// return the leftmost index equal to x or -1 if not found
return result;
}
編輯：
更改計(jì)算 mid 的方式以避免較大總和溢出
// Previously, can overflow since we add two integer
int mid = (min + max) / 2;
// Now
int mid = min + ((max - min) / 2);
// Another way using the unsigned right shift operator
int mid = (low + high) >>> 1;
// The left operands value (low + high) is moved right
// by the number of bits specified (2 in this case) by the right operand and
// shifted values are filled up with zeros.
// The >>> treats the value as unsigned
慕田峪7331174
TA貢獻(xiàn)1828條經(jīng)驗(yàn) 獲得超13個(gè)贊
這是相當(dāng)于lower_boundC++ 的搜索。它返回小于您要查找的值的元素?cái)?shù)量。這將是第一次出現(xiàn)的索引，或者如果沒有出現(xiàn)則將插入其中：
int numSmaller(int[] seq, int valueToFind)
{
? ? int pos=0;
? ? int limit=seq.length;
? ? while(pos<limit)
? ? {
? ? ? ? int testpos = pos+((limit-pos)>>1);
? ? ? ? if (seq[testpos]<valueToFind)
? ? ? ? ? ? pos=testpos+1;
? ? ? ? else
? ? ? ? ? ? limit=testpos;
? ? }
? ? return pos;
}
請(qǐng)注意，每次迭代我們只需要進(jìn)行一次比較。
鏈接的答案強(qiáng)調(diào)了以這種方式編寫二分搜索的幾個(gè)優(yōu)點(diǎn)。
斯蒂芬大帝
TA貢獻(xiàn)1827條經(jīng)驗(yàn) 獲得超8個(gè)贊
它認(rèn)為它會(huì)幫助你
public static boolean binarysearch(int[] data, int target, int low, int high){
if(low>high){
System.out.println("Target not found");
return false;}
else{
int mid=(low+high)/2;
if(target==data[mid])
return true;
else if(target<data[mid])
return binarysearch(data, target, low, high);
else
return binarysearch(data, target, low, high);
}
}
添加回答
舉報(bào)
0/150
提交
取消