二分探索は、ソートされたデータセットに対して行われるもので、探索の考え方は分割統治法に似ています。毎回、区間の中央の要素と比較して、探索する区間を前半または後半に縮小していきます。要素が見つかるか、区間が 0 に縮小されるまで続けます。
簡単な二分探索#
/**
*
* @param {Array} array ソートされた配列
* @param {Number} length 配列の長さ
* @param {Number} value 探索する値
* @returns 位置
*/
function bsearch(array, length, value) {
let left = 0;
let right = length - 1;
while (left <= right) {
let mid = (left + right) >> 1;
if (array[mid] === value) {
return mid;
} else if (array[mid] < value) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
再帰的な二分探索#
/**
*
* @param {Array} array ソートされた配列
* @param {Number} length 配列の長さ
* @param {Number} value 探索する値
* @returns 位置
*/
function bsearch(array, length, value) {
return bsearchInternal(array, 0, length - 1, value);
}
function bsearchInternal(array, left, right, value) {
if (left > right) return -1;
let mid = (left + right) >> 1;
if (array[mid] === value) {
return mid;
} else if (array[mid] < value) {
return bsearchInternal(array, mid + 1, right, value);
} else {
return bsearchInternal(array, left, mid - 1, value);
}
}
よくある二分探索の変形問題#
変形問題 1:与えられた値と等しい最初の要素を探す#
/**
*
* @param {Array} array ソートされた配列
* @param {Number} length 配列の長さ
* @param {Number} value 探索する値
* @returns 位置
*/
function bsearch(array, length, value) {
let left = 0;
let right = length - 1;
while (left <= right) {
let mid = (left + right) >> 1;
if (array[mid] > value) {
right = mid - 1;
} else if (array[mid] < value) {
left = mid + 1;
} else {
if (mid === 0 || (array[mid - 1] !== value)) {
return mid
} else {
right = mid - 1;
}
}
}
return -1;
}
変形問題 2:与えられた値と等しい最後の要素を探す#
/**
*
* @param {Array} array ソートされた配列
* @param {Number} length 配列の長さ
* @param {Number} value 探索する値
* @returns 位置
*/
function bsearch(array, length, value) {
let left = 0;
let right = length - 1;
while (left <= right) {
let mid = (left + right) >> 1;
if (array[mid] > value) {
right = mid - 1;
} else if (array[mid] < value) {
left = mid + 1;
} else {
if ((array[mid + 1] !== value) || (mid === (length - 1))) {
return mid;
} else {
left = mid + 1;
}
}
}
return -1;
}
変形問題 3:与えられた値以上の最初の要素を探す#
/**
*
* @param {Array} array ソートされた配列
* @param {Number} length 配列の長さ
* @param {Number} value 探索する値
* @returns 位置
*/
function bsearch(array, length, value) {
let left = 0;
let right = length - 1;
while (left <= right) {
let mid = (left + right) >> 1;
if (array[mid] >= value) {
if ((array[mid - 1] < value) || (mid === 0)) {
return mid;
} else {
right = mid - 1
}
} else {
left = mid + 1;
}
}
return -1;
}
変形問題 4:与えられた値以下の最後の要素を探す#
/**
*
* @param {Array} array ソートされた配列
* @param {Number} length 配列の長さ
* @param {Number} value 探索する値
* @returns 位置
*/
function bsearch(array, length, value) {
let left = 0;
let right = length - 1;
while (left <= right) {
let mid = (left + right) >> 1;
if (array[mid] <= value) {
if ((array[mid + 1] > value) || (mid === length - 1)) {
return mid;
} else {
left = mid + 1
}
} else {
right = mid - 1;
}
}
return -1;
}