如何使用递归创建二进制搜索-Java 学习之路

我试图写一个我以前从未做过的“二分搜索” . 当搜索的值是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

Code

//_________________________________________________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
    }
}

6 回答

你错了 .

使用此代码：

//_________________________________________________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;
    }
}

此外，如果搜索元素不在数组中，这将无限期地继续 . 为此添加基础案例 .

回复于 2024-05-02T08:45:15+08:00

3
语言不可知，这里是递归二进制搜索实现的简化流程，假设我们有一个（最初非空）数组[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
```
以下是执行上述控制流程的解决方案 . 这类似于本文中已经提出的解决方案，但有一些值得注意的差异：
```
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)
  }
}
```
让我们解开这个实现的主要区别：
- Slice is no longer used:
我们避免使用Array.prototype.slice，因为它是一个相对昂贵的操作（每次递归调用复制当前数组的一半！）并且算法不需要正常运行 .

代替切片，我们传递了我们将搜索范围缩小到的数组范围的起始和停止索引 . 这使得我们的堆快乐不会因为（可能很多）部分的，非常复制的同一（潜在的大量）数组而混乱 .
- We are passing two additional arguments, and they have defaults:
这些参数（开始和停止）用于跟踪我们当前重复出现的数组的范围 . 它们是切片的替代品！默认参数使我们能够像使用切片时那样调用此递归函数（如果用户在首次调用时不提供显式范围） .
- We are using a switch statement:
switch语句与if-else链的速度取决于几个因素，最值得注意的是编程语言和每个因素的条件数量 . 这里使用switch语句主要是为了提高可读性 . 它是一个控制流，它与我们在这个递归函数中处理的处理相匹配：4个离散的情况，每个都需要不同的动作 . 此外，少数人对超过3次逻辑测试的if-else语句有罕见的过敏反应 . 有关JavaScript的switch语句及其性能与if-else的更多信息，请查看这篇文章：Javascript switch vs. if...else if...else，链接到这个更具信息性的页面http://archive.oreilly.com/pub/a/server-administration/excerpts/even-faster-websites/writing-efficient-javascript.html
回复于 2024-05-02T08:45:15+08:00
0
我认为这一行：
```
var newArr = arr.slice(0, arr[midPoint]);
```
应该是：
```
var newArr = arr.slice(0, midPoint);
```
但我不知道这是否是您代码的唯一问题 . （我不清楚代码应该实际做什么 . 现在“getMidPoint”似乎返回一个包含搜索值的较小数组 . ）
回复于 2024-05-02T08:45:15+08:00

这是完全重写的代码，以实现您的目标（评论，linted） . 此示例没有对params的任何检查 .

主要错误：

错切片

这种方法的缺点：

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 ) );

回复于 2024-05-02T08:45:15+08:00

您的代码中有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];
    }
}

如果在数组中找不到元素，则此函数将返回undefined .

回复于 2024-05-02T08:45:15+08:00

这是我的递归二进制搜索解决方案：

// 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)
  }

}

回复于 2024-05-02T08:45:15+08:00

如何使用递归创建二进制搜索

6 回答

相关问题