Open OPY-bbt opened 4 years ago
const mock_data = [1, 2, 3, 5, 9];
function bsearchRecursion (array, value) {
return bsearchRecursionInternally(array, value, 0, array.length - 1);
}
function bsearchRecursionInternally(array, value, low, high) {
if (low > high) return -1;
let mid = Math.floor((low + high) / 2);
if (array[mid] === value) {
return mid;
} else if (array[mid] > value){
return bsearchRecursionInternally(array, value, low, mid - 1);
} else {
return bsearchRecursionInternally(array, value, mid + 1, high);
}
}
document.body.innerHTML = bsearchRecursion(mock_data, 9);
function squareRoot(value) {
let low = 0;
let high = value;
let mid = (low + high) / 2;
while(Math.abs(mid * mid - value) >= 1e-6 ) {
mid = (low + high) / 2;
if (mid * mid > value) {
high = mid;
} else if (mid * mid < value) {
low = mid;
}
}
return mid.toFixed(6);
}
document.body.innerHTML = squareRoot(10);
const mock_data = [1, 1, 2, 2, 3, 4, 9, 9];
// 变体一: 查找第一个值等于给定值的元素
function bsearch1(array, value) {
let low = 0;
let high = array.length - 1;
while (low <= high) {
const mid = Math.floor((low + high) / 2);
if (array[mid] > value) {
high = mid - 1;
} else if (array[mid] < value) {
low = mid + 1;
} else {
// 相等的情况,再看前面的值是否相等,如果相等调节high;
if (mid > 0 && array[mid - 1] === value) {
high = mid - 1;
} else {
return mid;
}
}
}
return -1;
}
// 变体二: 查找最后一个值等于给定植的元素
function bsearch2(array, value) {
let low = 0;
let high = array.length - 1;
while(low <= high) {
let mid = Math.floor((low + high) / 2);
if (array[mid] > value) {
high = mid - 1;
} else if (array[mid] < value) {
low = mid + 1;
} else {
if (mid < array.length - 1 && array[mid + 1] === value) {
low = mid + 1;
} else {
return mid;
}
}
}
return -1;
}
// 变体三: 查找第一个大于等于给定值的元素
function bsearch3(array, value) {
let low = 0;
let high = array.length - 1;
while(low <= high) {
let mid = Math.floor((low + high) / 2);
if (array[mid] >= value) {
if (mid === 0 || array[mid - 1] < value) {
return mid;
}
high = mid - 1;
} else {
low = mid + 1;
}
}
return -1;
}
// 变体四: 查找最后一个小于等于给给定值的元素
function bsearch4(array, value) {
let low = 0;
let high = array.length - 1;
while(low <= high) {
let mid = Math.floor((low + high) / 2);
if (array[mid] <= value) {
if (mid === array.length - 1 || array[mid + 1] > value) {
return mid;
}
low = mid + 1;
} else {
high = mid - 1;
}
}
}
document.body.innerHTML = bsearch4(mock_data, 1);
循环