我想找到一個目標值 4 在序列 [1, 1, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 6] 中首先出現的位置。當我使用 java.util.Arrays.binaySearch 時，它返回索引是 9，但我期望的是 7。我看java.util.Arrays.binaySearch我發現了一些評論：如果數組包含多個具有指定值的元素，則無法保證找到哪一個。那么如何在Java中實現一個lower_bound二分查找算法，返回目標值就首先出現了。注意：lower_bound概念來自C++，但我不太了解C++。
3 回答
當年話下
TA貢獻1890條經驗 獲得超9個贊
我認為下面的實現將正確完成工作：
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
慕田峪7331174
TA貢獻1828條經驗 獲得超13個贊
這是相當于lower_boundC++ 的搜索。它返回小于您要查找的值的元素數量。這將是第一次出現的索引，或者如果沒有出現則將插入其中：
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;
}
請注意，每次迭代我們只需要進行一次比較。
鏈接的答案強調了以這種方式編寫二分搜索的幾個優點。
斯蒂芬大帝
TA貢獻1827條經驗 獲得超8個贊
它認為它會幫助你
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
提交
取消