如何使用递归创建二分查找
How to create a binary search with recursion
我正在尝试写一个我以前从未写过的 "binary search"。当搜索的值为 6 或 2 时，下面的代码不起作用，我想知道我做错了什么以及如何补救。
编辑
为了解释它应该做什么（根据我的理解），二分搜索要求数组已经排序，然后查找数组的中点索引。例如，如果一个数组有九个索引 (0-8)，则中点将为索引 4。
var arr = [1, 2, 3, 4, 5, 6, 7, 8, 9];
算法然后确定该中点的值是否高于或低于您正在搜索的数字。数组一侧不包含搜索数字且存在于中点值之前的所有元素都将被删除。如果搜索值是 8 那么结果将是：
[ 1, 2, 3, 4, 5, 6, 7, 8, 9 ]
array midpoint value: 5
[ 5, 6, 7, 8, 9 ]
array midpoint value: 7
[ 7, 8, 9 ]
array midpoint value: 8
代码
//_________________________________________________BEGIN notes
// Step 1. Get length of array
// Step 2. Find mid point
// Step 3. Compare if mid point is lower or higher than searched number
// Step 4. lop off unneeded side
// Step 5. go to step 1
//_________________________________________________END notes
var arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 44, 55];
function getMidPoint(arr, searchNumb) {
var length = arr.length;
var midPoint = Math.floor(length / 2);
var newArr = arr;
console.log(arr);
console.log("array midpoint value: " + arr[midPoint]);
if (arr[midPoint] > searchNumb) {
var newArr = arr.slice(0, arr[midPoint]);
return getMidPoint(newArr, searchNumb);
} else if (arr[midPoint] < searchNumb) {
var newArr = arr.slice(midPoint, arr.length);
return getMidPoint(newArr, searchNumb);
} else {
return arr
}
}
我认为这一行：
var newArr = arr.slice(0, arr[midPoint]);
大概应该是：
var newArr = arr.slice(0, midPoint);
但我不知道这是否是您的代码的唯一问题。 （我不清楚代码实际上应该做什么。现在 "getMidPoint" 似乎 returns 包含搜索值的较小数组。）
- 你切错了。
使用此代码：
//_________________________________________________BEGIN notes
// Step 1. Get length of array
// Step 2. Find mid point
// Step 3. Compare if mid point is lower or higher than searched number
// Step 4. lop off unneeded side
// Step 5. go to step 1
//_________________________________________________END notes
var arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 44, 55];
function getMidPoint(arr, searchNumb) {
var length = arr.length;
var midPoint = Math.floor(length / 2);
var newArr = arr;
console.log(arr);
console.log("array midpoint value: " + arr[midPoint]);
if (arr[midPoint] > searchNumb) {
var newArr = arr.slice(0, midPoint);
return getMidPoint(newArr, searchNumb);
} else if (arr[midPoint] < searchNumb) {
var newArr = arr.slice(midPoint + 1, arr.length);
return getMidPoint(newArr, searchNumb);
} else {
return midPoint;
}
}
- 另外，如果搜索元素不在数组中，这将无限进行下去。也为此添加一个基本案例。
您的代码中有 2 个问题：-
1) 你切错了
2) 你没有设置任何基础条件
这段代码应该可以正常工作：-
var arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 44, 55];
function getMidPoint(arr, searchNumb) {
var length = arr.length;
var midPoint = Math.floor(length / 2);
var newArr = arr;
console.log(arr);
console.log("array midpoint value: " + arr[midPoint]);
if (arr[midPoint] > searchNumb) {
var newArr = arr.slice(0, midPoint);
return getMidPoint(newArr, searchNumb);
} else if (arr[midPoint] < searchNumb) {
var newArr = arr.slice(midPoint+1, arr.length);
return getMidPoint(newArr, searchNumb);
} else {
return arr[midPoint];
}
}
如果在数组中找不到元素，则此函数将return未定义。
与语言无关，这里是递归二进制搜索实现的简化流程，假设我们有一个（最初非空的）数组 [ARR] 和一个目标 [T]，我们指的是 ARR 的中间元素作为 M:
// 1. If M == T, return true
// 2. If length of ARR is 0, return false (note: step 1 short circuits, ensuring we only hit step 2 if step 1 evaluates to false)
// 3. If T < M, return the result of the recursion on the lower half of ARR
// 4. If T > M, return the result of the recursion on the the latter half of ARR
以下是执行上述控制流的解决方案。这与本 post 中已经提出的解决方案类似，但有一些值得注意的差异：
function binarySearch(arr, target, start=0, stop=(arr.length-1)) {
let midPoint = Math.floor(((stop-start)/2) + start)
switch (true) {
case arr[midPoint] === target:
return true
case stop - start === 0:
return false
case arr[midPoint] < target:
return binarySearch(arr, target, midPoint+1, stop)
case arr[midPoint] > target:
return binarySearch(arr, target, start, midPoint)
}
}
让我们来解开这个实现的主要区别：
切片不再使用：
我们避免使用 Array.prototype.slice 因为它是一个相对昂贵的操作（每次递归调用复制当前数组的一半！）并且算法正常运行不需要它。
代替切片，我们正在传递我们已缩小搜索范围的数组范围的开始和结束索引。这让我们的堆保持快乐，因为它不会被相同（可能大量）数组的（可能很多）部分的、非永久的副本弄得乱七八糟。
我们传递了两个额外的参数，它们有默认值：
这些参数（开始和停止）用于跟踪我们当前重复出现的数组范围。它们是我们切片的替代品！
默认参数使我们能够像使用 slice 时一样调用这个递归函数（如果用户在第一次调用时不提供明确的范围）。
我们正在使用 switch 语句：
switch 语句与 if-else 链的速度取决于几个因素，最显着的是编程语言和每个条件中的条件数量。此处使用 switch 语句主要是为了提高可读性。它是一个控制流，与我们在这个递归函数中所关注的处理相匹配：4 个离散的情况，每个都需要不同的操作。此外，一些人对超过 3 个逻辑测试的 if-else 语句有罕见的过敏。
有关 JavaScript 的 switch 语句及其性能与 if-else 的更多信息，请查看此 post：Javascript switch vs. if...else if...else, which links to this more informative page http://archive.oreilly.com/pub/a/server-administration/excerpts/even-faster-websites/writing-efficient-javascript.html
这是为实现您的目标而完全重写的代码（已注释、已检查）。
此示例没有对参数进行任何检查。
主要错误：
- 切片错误
这种方法的缺点：
recursion 速度较慢并且占用更多堆栈slice()也不需要（因为又是栈）
/**
* Searches recursively number from the list
* @param {Array} list
* @param {number} item Search item
* @param {number} low Lower limit of search in the list
* @param {number} high Highest limit of search in the list
* @param {number} arrLength Length of the list
* @return {(number | null)} Number if the value is found or NULL otherwise
*/
const binarySearch = ( list, item, low, high, arrLength ) => {
while ( low <= high ) {
let mid = Math.floor((low + high) / 2);
let guess = list[mid];
if ( guess === item ) {
return mid;
} else if ( guess > item ) {
high = mid - 1;
list = list.slice( 0, mid );
return binarySearch( list, item, low, high );
} else {
low = mid + 1;
list = list.slice( low, arrLength );
return binarySearch( list, item, low, high );
}
}
return null;
};
/**
* Creates the array that contains numbers 1...N
* @param {number} n - number N
* @return {Array}
*/
const createArr = ( n ) => Array.from({length: n}, (v, k) => k + 1);
const myList = createArr( 100 );
const arrLength = myList.length;
let low = 0;
let high = arrLength - 1;
console.log( '3 ' + binarySearch( myList, 3, low, high, arrLength ) ); // 2
console.log( '-1 ' + binarySearch( myList, -1, low, high, arrLength ) ); // null
我认为它是更优雅的二进制搜索解决方案：
const binarySearch = ( list, item ) => {
let low = 0;
let high = list.length - 1;
while ( low <= high ) {
let mid = Math.floor((low + high) / 2);
let guess = list[mid];
if ( guess === item ) {
return mid;
} else if ( guess > item ) {
high = mid - 1;
} else {
low = mid + 1;
}
}
return null;
};
const myList = [1, 3, 5, 7, 9];
console.log( binarySearch( myList, 3 ) );
console.log( binarySearch( myList, -1 ) );
这是我的递归二进制搜索解决方案：
// arr = sorted array, val = search value
// left and right are the index pointers enclosing the search value
// e.g. binarySearch([1,5,7,9,14,17,24,29,33,38,49,52,61,62,70,80,90,95,104,107,109],70)
binarySearch = (arr,val,left=0,right=arr.length) => {
position = (left,right) => {
let pos = (left + right)/2
return Math.floor(pos)
}
let i = position(left,right)
if (arr[i] === val) {
return i
}
// Base Case: if left and midpoint index coincide then there are no more possible solutions
else if (i === left) {
return -1
}
// For this case we shift the left index pointer
else if (arr[i] < val) {
return binarySearch(arr,val,i,right)
}
// For this case we shift the right index pointer
else if (arr[i] > val) {
return binarySearch(arr,val,left,i)
}
}
这是我的递归二进制搜索方法。
我们不对数组进行切片，因为如果我们只传递索引就不需要它了。
我认为这会节省一些时间。
如果找到元素，函数将 return 建立索引，如果找不到则为 -1。
l代表左边，r代表右边
function binarySearch(arr, searchNumber) {
return _binarySearch(0, arr.length -1, arr, searchNumber);
function _binarySearch(l, r, arr, searchNumber) {
const mid = Math.floor((l + r) / 2);
const guess = arr[mid];
if (guess === searchNumber) { // base case
return mid;
} else if (l === r) { // end-case the element is not in the array
return -1;
} else if (guess < searchNumber) {
return _binarySearch(mid + 1, arr.length - 1, arr, searchNumber);
} else if (guess > searchNumber) {
return _binarySearch(l, mid - 1, arr, searchNumber);
}
}
}
const list = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
console.log(binarySearch(list, 4));
简单易行
let arr = [1,2,3,4,5];
function BinarySearch(arr, start, end, key) {
if(start > end) return -1;
let mid = Math.floor((start + end) / 2);
if(arr[mid] === key) return mid;
if(key > arr[mid]) {
return BinarySearch(arr, mid + 1, end, key);
} else if(key < arr[mid]) {
return BinarySearch(arr, start, mid -1, key);
}
}
BinarySearch([1,3,4,5], 0, arr.length - 1, 1); // it will return 0;
可能您已经是二分查找的高手了。但是我想指出，没有必要创建滑动 window 来解析二进制搜索。
function binarySearch(arr, value){
if(!arr.length) return -1;
let average = Math.floor(arr.length-1/2);
if (value === arr[average]) return average;
if (value > arr[average]) return binarySearch(arr.slice(average+1),value);
if (value < arr[average]) return binarySearch(arr.slice(0,average),value);
}
binarySearch([1,2,3,4,5],6) //-1
binarySearch([1,2,3,4,5],3) //2
按照以下步骤创建带递归的二分搜索：
function binarySearch(arr, value){
1 ) 实施基本案例
if(!arr.length) return -1;
2 ) 创建一个中点
let average = Math.floor(arr.length-1/2);
3 ) 如果中间点等于搜索值，就找到了！ return价值
if (value === arr[average]) return average;
4) 如果值大于中间点运行 一个只有子数组从中间开始的新进程 + 1 直到结束
if (value > arr[average]) return binarySearch(arr.slice(average+1),value);
5)如果值低于中间点运行一个新进程，只有子数组从0开始到中间
if (value < arr[average]) return binarySearch(arr.slice(0,average),value);
}
希望对您有所帮助！
注意：为了不重复if,if,if可以使用switch语句，但我更喜欢这种方式，可读性更好。
要解决递归问题，请在下面找到答案和解释。
const BinarySearchRec = (arr, el) => {
// finding the middle index
const mid = Math.floor(arr.length / 2);
if (arr[mid] === el) {
// if the element is found then return the element.
return mid;
}
if (arr[mid] < el && mid < arr.length) {
/** here we are having the value returned from recursion as
the value can be -1 as well as a value which is in second half of the original array.**/
const retVal = BinarySearchRec(arr.slice(mid + 1, arr.length), el);
/** if value is greater than or equal to 0 then only add that value with mid
and also one as mid represents the index.
Since index starts from 0 we have to compensate it as we require the length here.**/
return retVal >= 0 ? mid + 1 + retVal : -1;
}
if (arr[mid] > el) {
// here we need not do any manipulation
return BinarySearchRec(arr.slice(0, mid), el);
}
return -1;
};
以上解决方案已添加并接受的解决方案在要查找的元素在后半部分的场景中失败。
有 while 循环的解决方案可以正常工作，但由于问题是递归解决它，我给出了一个全面的递归版本。
BinarySearch 递归返回搜索元素索引。
下面的代码对我有用
function binerySearchRecursive(arr, num, start=0 end=arr.length-1){
let mid = Math.floor((start+end/2));
if(start> end){
return -1; // edge case if array has 1 element or 0
}
if(num === arr[mid])
return mid;
else if(num < arr[mid])
return binerySearchRecursive(arr, num, start, mid-1 );
else
return binerySearchRecursive(arr, num, mid+1 , end);
}
binerySearchRecursive([1,2,3,4,5], 5)
function binarySearch(arr, n) {
let mid = Math.floor(arr.length / 2);
// Base case
if (n === arr[mid]) {
return mid;
}
//Recursion
if (n > arr[mid]) {
return mid + binarySearch(arr.slice(mid, arr.length), n)
} else {
return binarySearch(arr.slice(0, mid), n)
} }
递归二分查找的简单解决方案
对于递归二分搜索，您可以试试这个：
function recursiveBinarySearch(lst, target, start=0, end=(lst.length-1)){
let midPoint = (Math.floor((start+end)/2));
if (start > end){
return false;
}
if (lst[midPoint] === target){
return true;
}
else{
if(lst[midPoint] < target){
return recursiveBinarySearch(lst, target, midPoint+1, end);
}
else{
return recursiveBinarySearch(lst, target, start, midPoint-1);
}
}
}
这太晚了，但我希望这对某些人有用:)
const items = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15];
let target = 30;
function binarySearch(L,R){
if(L == R){
return false;
}
let mid = Math.floor((L + R)/2);
if(mid == target){
return target;
}
if(mid > target){
binarySearch(L,mid);
}
if(mid < target){
binarySearch(mid+1,R);
}
}
binarySearch(1,items.length);
我正在尝试写一个我以前从未写过的 "binary search"。当搜索的值为 6 或 2 时，下面的代码不起作用，我想知道我做错了什么以及如何补救。
编辑
为了解释它应该做什么（根据我的理解），二分搜索要求数组已经排序，然后查找数组的中点索引。例如，如果一个数组有九个索引 (0-8)，则中点将为索引 4。
var arr = [1, 2, 3, 4, 5, 6, 7, 8, 9];
算法然后确定该中点的值是否高于或低于您正在搜索的数字。数组一侧不包含搜索数字且存在于中点值之前的所有元素都将被删除。如果搜索值是 8 那么结果将是：
[ 1, 2, 3, 4, 5, 6, 7, 8, 9 ]
array midpoint value: 5
[ 5, 6, 7, 8, 9 ]
array midpoint value: 7
[ 7, 8, 9 ]
array midpoint value: 8
代码
//_________________________________________________BEGIN notes
// Step 1. Get length of array
// Step 2. Find mid point
// Step 3. Compare if mid point is lower or higher than searched number
// Step 4. lop off unneeded side
// Step 5. go to step 1
//_________________________________________________END notes
var arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 44, 55];
function getMidPoint(arr, searchNumb) {
var length = arr.length;
var midPoint = Math.floor(length / 2);
var newArr = arr;
console.log(arr);
console.log("array midpoint value: " + arr[midPoint]);
if (arr[midPoint] > searchNumb) {
var newArr = arr.slice(0, arr[midPoint]);
return getMidPoint(newArr, searchNumb);
} else if (arr[midPoint] < searchNumb) {
var newArr = arr.slice(midPoint, arr.length);
return getMidPoint(newArr, searchNumb);
} else {
return arr
}
}
我认为这一行：
var newArr = arr.slice(0, arr[midPoint]);
大概应该是：
var newArr = arr.slice(0, midPoint);
但我不知道这是否是您的代码的唯一问题。 （我不清楚代码实际上应该做什么。现在 "getMidPoint" 似乎 returns 包含搜索值的较小数组。）
- 你切错了。
使用此代码：
//_________________________________________________BEGIN notes
// Step 1. Get length of array
// Step 2. Find mid point
// Step 3. Compare if mid point is lower or higher than searched number
// Step 4. lop off unneeded side
// Step 5. go to step 1
//_________________________________________________END notes
var arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 44, 55];
function getMidPoint(arr, searchNumb) {
var length = arr.length;
var midPoint = Math.floor(length / 2);
var newArr = arr;
console.log(arr);
console.log("array midpoint value: " + arr[midPoint]);
if (arr[midPoint] > searchNumb) {
var newArr = arr.slice(0, midPoint);
return getMidPoint(newArr, searchNumb);
} else if (arr[midPoint] < searchNumb) {
var newArr = arr.slice(midPoint + 1, arr.length);
return getMidPoint(newArr, searchNumb);
} else {
return midPoint;
}
}
- 另外，如果搜索元素不在数组中，这将无限进行下去。也为此添加一个基本案例。
您的代码中有 2 个问题：-
1) 你切错了 2) 你没有设置任何基础条件
这段代码应该可以正常工作：-
var arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 44, 55];
function getMidPoint(arr, searchNumb) {
var length = arr.length;
var midPoint = Math.floor(length / 2);
var newArr = arr;
console.log(arr);
console.log("array midpoint value: " + arr[midPoint]);
if (arr[midPoint] > searchNumb) {
var newArr = arr.slice(0, midPoint);
return getMidPoint(newArr, searchNumb);
} else if (arr[midPoint] < searchNumb) {
var newArr = arr.slice(midPoint+1, arr.length);
return getMidPoint(newArr, searchNumb);
} else {
return arr[midPoint];
}
}
如果在数组中找不到元素，则此函数将return未定义。
与语言无关，这里是递归二进制搜索实现的简化流程，假设我们有一个（最初非空的）数组 [ARR] 和一个目标 [T]，我们指的是 ARR 的中间元素作为 M:
// 1. If M == T, return true
// 2. If length of ARR is 0, return false (note: step 1 short circuits, ensuring we only hit step 2 if step 1 evaluates to false)
// 3. If T < M, return the result of the recursion on the lower half of ARR
// 4. If T > M, return the result of the recursion on the the latter half of ARR
以下是执行上述控制流的解决方案。这与本 post 中已经提出的解决方案类似，但有一些值得注意的差异：
function binarySearch(arr, target, start=0, stop=(arr.length-1)) {
let midPoint = Math.floor(((stop-start)/2) + start)
switch (true) {
case arr[midPoint] === target:
return true
case stop - start === 0:
return false
case arr[midPoint] < target:
return binarySearch(arr, target, midPoint+1, stop)
case arr[midPoint] > target:
return binarySearch(arr, target, start, midPoint)
}
}
让我们来解开这个实现的主要区别：
切片不再使用：
我们避免使用 Array.prototype.slice 因为它是一个相对昂贵的操作（每次递归调用复制当前数组的一半！）并且算法正常运行不需要它。
代替切片，我们正在传递我们已缩小搜索范围的数组范围的开始和结束索引。这让我们的堆保持快乐，因为它不会被相同（可能大量）数组的（可能很多）部分的、非永久的副本弄得乱七八糟。
我们传递了两个额外的参数，它们有默认值：
这些参数（开始和停止）用于跟踪我们当前重复出现的数组范围。它们是我们切片的替代品！ 默认参数使我们能够像使用 slice 时一样调用这个递归函数（如果用户在第一次调用时不提供明确的范围）。
我们正在使用 switch 语句：
switch 语句与 if-else 链的速度取决于几个因素，最显着的是编程语言和每个条件中的条件数量。此处使用 switch 语句主要是为了提高可读性。它是一个控制流，与我们在这个递归函数中所关注的处理相匹配：4 个离散的情况，每个都需要不同的操作。此外，一些人对超过 3 个逻辑测试的 if-else 语句有罕见的过敏。 有关 JavaScript 的 switch 语句及其性能与 if-else 的更多信息，请查看此 post：Javascript switch vs. if...else if...else, which links to this more informative page http://archive.oreilly.com/pub/a/server-administration/excerpts/even-faster-websites/writing-efficient-javascript.html
这是为实现您的目标而完全重写的代码（已注释、已检查）。 此示例没有对参数进行任何检查。
主要错误：
- 切片错误
这种方法的缺点：
recursion速度较慢并且占用更多堆栈slice()也不需要（因为又是栈）
/**
* Searches recursively number from the list
* @param {Array} list
* @param {number} item Search item
* @param {number} low Lower limit of search in the list
* @param {number} high Highest limit of search in the list
* @param {number} arrLength Length of the list
* @return {(number | null)} Number if the value is found or NULL otherwise
*/
const binarySearch = ( list, item, low, high, arrLength ) => {
while ( low <= high ) {
let mid = Math.floor((low + high) / 2);
let guess = list[mid];
if ( guess === item ) {
return mid;
} else if ( guess > item ) {
high = mid - 1;
list = list.slice( 0, mid );
return binarySearch( list, item, low, high );
} else {
low = mid + 1;
list = list.slice( low, arrLength );
return binarySearch( list, item, low, high );
}
}
return null;
};
/**
* Creates the array that contains numbers 1...N
* @param {number} n - number N
* @return {Array}
*/
const createArr = ( n ) => Array.from({length: n}, (v, k) => k + 1);
const myList = createArr( 100 );
const arrLength = myList.length;
let low = 0;
let high = arrLength - 1;
console.log( '3 ' + binarySearch( myList, 3, low, high, arrLength ) ); // 2
console.log( '-1 ' + binarySearch( myList, -1, low, high, arrLength ) ); // null
我认为它是更优雅的二进制搜索解决方案：
const binarySearch = ( list, item ) => {
let low = 0;
let high = list.length - 1;
while ( low <= high ) {
let mid = Math.floor((low + high) / 2);
let guess = list[mid];
if ( guess === item ) {
return mid;
} else if ( guess > item ) {
high = mid - 1;
} else {
low = mid + 1;
}
}
return null;
};
const myList = [1, 3, 5, 7, 9];
console.log( binarySearch( myList, 3 ) );
console.log( binarySearch( myList, -1 ) );
这是我的递归二进制搜索解决方案：
// arr = sorted array, val = search value
// left and right are the index pointers enclosing the search value
// e.g. binarySearch([1,5,7,9,14,17,24,29,33,38,49,52,61,62,70,80,90,95,104,107,109],70)
binarySearch = (arr,val,left=0,right=arr.length) => {
position = (left,right) => {
let pos = (left + right)/2
return Math.floor(pos)
}
let i = position(left,right)
if (arr[i] === val) {
return i
}
// Base Case: if left and midpoint index coincide then there are no more possible solutions
else if (i === left) {
return -1
}
// For this case we shift the left index pointer
else if (arr[i] < val) {
return binarySearch(arr,val,i,right)
}
// For this case we shift the right index pointer
else if (arr[i] > val) {
return binarySearch(arr,val,left,i)
}
}
这是我的递归二进制搜索方法。
我们不对数组进行切片，因为如果我们只传递索引就不需要它了。 我认为这会节省一些时间。
如果找到元素，函数将 return 建立索引，如果找不到则为 -1。
l代表左边，r代表右边
function binarySearch(arr, searchNumber) {
return _binarySearch(0, arr.length -1, arr, searchNumber);
function _binarySearch(l, r, arr, searchNumber) {
const mid = Math.floor((l + r) / 2);
const guess = arr[mid];
if (guess === searchNumber) { // base case
return mid;
} else if (l === r) { // end-case the element is not in the array
return -1;
} else if (guess < searchNumber) {
return _binarySearch(mid + 1, arr.length - 1, arr, searchNumber);
} else if (guess > searchNumber) {
return _binarySearch(l, mid - 1, arr, searchNumber);
}
}
}
const list = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
console.log(binarySearch(list, 4));
简单易行
let arr = [1,2,3,4,5];
function BinarySearch(arr, start, end, key) {
if(start > end) return -1;
let mid = Math.floor((start + end) / 2);
if(arr[mid] === key) return mid;
if(key > arr[mid]) {
return BinarySearch(arr, mid + 1, end, key);
} else if(key < arr[mid]) {
return BinarySearch(arr, start, mid -1, key);
}
}
BinarySearch([1,3,4,5], 0, arr.length - 1, 1); // it will return 0;
可能您已经是二分查找的高手了。但是我想指出，没有必要创建滑动 window 来解析二进制搜索。
function binarySearch(arr, value){
if(!arr.length) return -1;
let average = Math.floor(arr.length-1/2);
if (value === arr[average]) return average;
if (value > arr[average]) return binarySearch(arr.slice(average+1),value);
if (value < arr[average]) return binarySearch(arr.slice(0,average),value);
}
binarySearch([1,2,3,4,5],6) //-1
binarySearch([1,2,3,4,5],3) //2
按照以下步骤创建带递归的二分搜索：
function binarySearch(arr, value){
1 ) 实施基本案例
if(!arr.length) return -1;
2 ) 创建一个中点
let average = Math.floor(arr.length-1/2);
3 ) 如果中间点等于搜索值，就找到了！ return价值
if (value === arr[average]) return average;
4) 如果值大于中间点运行 一个只有子数组从中间开始的新进程 + 1 直到结束
if (value > arr[average]) return binarySearch(arr.slice(average+1),value);
5)如果值低于中间点运行一个新进程，只有子数组从0开始到中间
if (value < arr[average]) return binarySearch(arr.slice(0,average),value);
}
希望对您有所帮助！
注意：为了不重复if,if,if可以使用switch语句，但我更喜欢这种方式，可读性更好。
要解决递归问题，请在下面找到答案和解释。
const BinarySearchRec = (arr, el) => {
// finding the middle index
const mid = Math.floor(arr.length / 2);
if (arr[mid] === el) {
// if the element is found then return the element.
return mid;
}
if (arr[mid] < el && mid < arr.length) {
/** here we are having the value returned from recursion as
the value can be -1 as well as a value which is in second half of the original array.**/
const retVal = BinarySearchRec(arr.slice(mid + 1, arr.length), el);
/** if value is greater than or equal to 0 then only add that value with mid
and also one as mid represents the index.
Since index starts from 0 we have to compensate it as we require the length here.**/
return retVal >= 0 ? mid + 1 + retVal : -1;
}
if (arr[mid] > el) {
// here we need not do any manipulation
return BinarySearchRec(arr.slice(0, mid), el);
}
return -1;
};
以上解决方案已添加并接受的解决方案在要查找的元素在后半部分的场景中失败。
有 while 循环的解决方案可以正常工作，但由于问题是递归解决它，我给出了一个全面的递归版本。
BinarySearch 递归返回搜索元素索引。 下面的代码对我有用
function binerySearchRecursive(arr, num, start=0 end=arr.length-1){
let mid = Math.floor((start+end/2));
if(start> end){
return -1; // edge case if array has 1 element or 0
}
if(num === arr[mid])
return mid;
else if(num < arr[mid])
return binerySearchRecursive(arr, num, start, mid-1 );
else
return binerySearchRecursive(arr, num, mid+1 , end);
}
binerySearchRecursive([1,2,3,4,5], 5)
function binarySearch(arr, n) {
let mid = Math.floor(arr.length / 2);
// Base case
if (n === arr[mid]) {
return mid;
}
//Recursion
if (n > arr[mid]) {
return mid + binarySearch(arr.slice(mid, arr.length), n)
} else {
return binarySearch(arr.slice(0, mid), n)
} }
递归二分查找的简单解决方案
对于递归二分搜索，您可以试试这个：
function recursiveBinarySearch(lst, target, start=0, end=(lst.length-1)){
let midPoint = (Math.floor((start+end)/2));
if (start > end){
return false;
}
if (lst[midPoint] === target){
return true;
}
else{
if(lst[midPoint] < target){
return recursiveBinarySearch(lst, target, midPoint+1, end);
}
else{
return recursiveBinarySearch(lst, target, start, midPoint-1);
}
}
}
这太晚了，但我希望这对某些人有用:)
const items = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15];
let target = 30;
function binarySearch(L,R){
if(L == R){
return false;
}
let mid = Math.floor((L + R)/2);
if(mid == target){
return target;
}
if(mid > target){
binarySearch(L,mid);
}
if(mid < target){
binarySearch(mid+1,R);
}
}
binarySearch(1,items.length);