16二分法查找
小于 1 分钟
二分法查找
前提条件:数据是有序的 二分法查找,取数据中间数值 m=数据长度/2
(向下取整或向上取整),把数据分成左右2个区间的数据(从小到大排序),m与需要查找的数值k比较,如果符合,则找到,否则,如果 k<m
在左边的数据区间继续二分查找,如果 k>m
在右边的数据区间继续二分查找,直到查找到最后一个数据,如果找到则返回 位置
,找不到返回 -1
二分法查找与变体的二分法查找
/*
* @Author: HotSuitor
* @Date: 2020-03-09 18:05:17
* @LastEditors: hs
* @LastEditTime: 2020-03-10 12:06:16
* @Description: hotsuitor@qq.com
*/
/**
* @description: 二分法查找
* @param {Array} arr=有序数组
* @param {Number} value=查找的值
* @return: index 匹配的下标 or -1
*/
function binarySearch(arr, value) {
let low = 0;
let high = arr.length - 1;
while (low <= high) {
let mid = low + ((high - low) >> 1);
if (value == arr[mid]) {
return mid;
} else if (value < arr[mid]) {
high = mid - 1;
} else {
low = mid + 1;
}
}
return -1;
}
let arr1 = [2, 3, 5, 7];
let value = 5;
let index = binarySearch(arr1, 5);
console.log(
`在[${arr1}]中查找${value},所在位置${index},arr1[${index}]=${value}`
);
/**
* @description: 查找第一个等于value的元素
* @param {Array} arr
* @param {Number} value
* @return:
*/
function binarySearchFirst(arr, value) {
let low = 0;
let high = arr.length - 1;
while (low <= high) {
let mid = low + ((high - low) >> 1);
if (arr[mid] < value) {
low = mid + 1;
} else if (arr[mid] > value) {
high = mid - 1;
} else {
if (mid == 0 || arr[mid - 1] != value) {
return mid;
} else {
high = mid - 1;
}
}
}
return -1;
}
value = 5;
let arr2 = [2, 3, 3, 5, 5, 7, 9, 9, 9, 11];
let index2 = binarySearchFirst(arr2, value);
console.log(
`在[${arr2}]中查找第一个等于${value}的元素,所在位置${index2},arr2[${index2}]=${value}`
);
/**
* @description: 查找最后一个值等于给定值的元素
* @param {Array} arr
* @param {Number} value
* @return: index=元素下标
*/
function binarySearchLast(arr, value) {
let low = 0;
let high = arr.length - 1;
while (low <= high) {
let mid = low + ((high - low) >> 1);
if (arr[mid] > value) {
high = mid - 1;
} else if (arr[mid] < value) {
low = mid + 1;
} else {
if (mid == arr.length - 1 || arr[mid + 1] != value) return mid;
else low = mid + 1;
}
}
return -1;
}
let index3 = binarySearchLast(arr2, value);
console.log(
`在[${arr2}]中查找最后一个等于${value}的元素,所在位置${index3},arr2[${index3}]=${value}`
);
/**
* @description: 查找第一个大于等于给定值的元素
* @param {Array} arr
* @param {Number} value
* @return: 找到元素的下标,找不到返回-1
*/
function binarySearchFirstGtE(arr, value) {
let low = 0;
let high = arr.length - 1;
while (low <= high) {
let mid = low + ((high - low) >> 1);
if (arr[mid] >= value) {
if (mid == 0 || arr[mid - 1] < value) return mid;
else high = mid - 1;
} else {
low = mid + 1;
}
}
return -1;
}
value = 9;
let index4 = binarySearchFirstGtE(arr2, value);
console.log(
`在[${arr2}]中查找第一个大于等于${value}的元素,所在位置${index4},arr2[${index4}]=${value}`
);
/**
* @description: 查找最后一个小于等于给定值的元素
* @param {Array} arr
* @param {Number} value
* @return: 找到元素的下标,找不到返回-1
*/
function binarySearchLastLtE(arr, value) {
let low = 0;
let high = arr.length - 1;
while (low <= high) {
let mid = low + ((high - low) >> 1);
if (arr[mid] <= value) {
if (mid == arr.length - 1 || arr[mid + 1] > value) return mid;
else low = mid + 1;
} else {
high = mid - 1;
}
}
return -1;
}
value = 9;
let index5 = binarySearchLastLtE(arr2, value);
console.log(
`在[${arr2}]中查找最后一个小于等于${value}的元素,所在位置${index5},arr2[${index5}]=${value}`
);