二分法
二分查找是一种高效搜索法，是一种可以在有序数组中搜索到特定元素的算法
优缺点
- 优：比较次数少，查找速度快，平均性能好，
- 缺: 要求待查表为有序表，且插入删除困难，
const arr = [2, 1, 3, 5, 6, 4, 7];
function bubbleSort(arr) {
if (!arr.length) return arr;
const copyArr = arr.slice();
for (let i = 0, length = copyArr.length; i < length; i++) {
for (let j = 0; j < length - i - 1; j++) {
const current = copyArr[j];
const next = copyArr[j + 1];
if (current > next) [copyArr[j], copyArr[j + 1]] = [next, current]
}
}
return copyArr;
}
const sortArr = bubbleSort(arr);
function binarySearch(arr, num, low = 0, height = arr.length || 0) {
const midIndex = Math.floor((low + height) / 2)
const midNum = arr[midIndex];
if (midNum === num) return [midIndex, midNum];
if (midNum > num) {
height = midIndex - 1;
return binarySearch(arr, num, low, height);
}
if (midNum < num) {
low = midIndex + 1;
return binarySearch(arr, num, low, height);
}
}
function binarySearch1(arr, num) {
let start = 0, end = arr.length, midNum, midIndex;
while (start <= end) {
midIndex = Math.floor((start + end) / 2);
midNum = arr[midIndex];
if (midNum === num) return {midNum, midIndex}
if (midNum > num) end = midIndex - 1;
else if (midNum < num) start = midIndex + 1
}
}
binarySearch1(sortArr, 3)
|
微信
