我想找到一個目標值 4 在序列 [1, 1, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 6] 中首先出現(xiàn)的位置。當(dāng)我使用 java.util.Arrays.binaySearch 時，它返回的索引是 9，但我預(yù)計是 7。我看java.util.Arrays.binaySearch源碼我發(fā)現(xiàn)了一些評論：如果數(shù)組包含多個具有指定值的元素，則無法保證找到哪一個。那么如何在Java中實現(xiàn)一個lower_bound二分查找算法，返回目標值最先出現(xiàn)的地方。注意：lower_bound的概念來自C++，但我對C++不是很了解。
3 回答
慕容708150
TA貢獻1831條經(jīng)驗 獲得超4個贊
我認為下面的實現(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;
}
編輯：
更改計算 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
海綿寶寶撒
TA貢獻1809條經(jīng)驗 獲得超8個贊
這是等同于從 C++ 進行的搜索lower_bound。它返回小于您要查找的值的元素數(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;
}
請注意，每次迭代我們只需要進行一次比較。
鏈接的答案強調(diào)了以這種方式編寫二進制搜索的幾個優(yōu)點。
慕無忌1623718
TA貢獻1744條經(jīng)驗 獲得超4個贊
它認為它會幫助你
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);
}
}
添加回答
舉報
0/150
提交
取消