二分検索実装の詳細
にぶんたんさく
第1部
public boolean ascendingFind(int[] arr, int start, int end, int value){
if (start > end) {
return false;
}
int mid = 0;
while(start < end){
mid = (start + end) >> 1;
if(arr[mid] < value){
start = mid + 1;
}else{
end = mid;
}
}
if (arr[end] == value) {
return true;
}
return false;
}第2部
1. a[]（ ）, m， m a /
一番左の位置は、a[mid]
// m , m a ， m
public int leftMostEqual(int[] a, int m){
int start = 0;
int end = a.length - 1;
int mid;
while(start < end){
mid = start + (end - start) / 2;
if (a[mid] < m) {
start = mid + 1;
}else {
end = mid;
}
}
return end;では、最後の戻り値はstart、end、midを取りますか?解析ではstart=end,midはまだ更新されていない可能性があるのでendを選択すべきである.また、mがaにない場合、上のコード出力はmの最初の下付き文字より大きい.ここでは次の質問に対応しています.
int[]aの中でm以上の一番左の下の記号を見つけます
の解は、実装上は完全に同じで、インタフェースは:
public int leftMostGreatEqual(int[] a, int m)次の質問は、aの中でmの一番右の位置を見つけて、上記の問題との違いは、start=mid+1はここでは使えません.a[start]=mの場合、現在のstartが最後の位置なのか、最初の位置なのか分からないので、右に移動することはできません.start=midしか使えません.このように、デッドサイクルを避けるために、while(start
// m , m a ， m
public int rightMostEqual(int[] a, int m){
int start = 0;
int end = a.length - 1;
int mid;
while(start < end - 1){
mid = start + (end - start) / 2;
if (a[mid] > m) {
end = mid - 1;
}else {
start = mid;
}
}
if(a[end] == m)
return end;
else {
return start;
}
} 終了条件をstart
このようにして、皆さんの質問と意見を歓迎します.