标签: binary-search

我几乎不好意思问这个问题，但无论出于何种原因，我都无法让它发挥作用。这是可汗学院关于二分搜索的练习。https://www.khanacademy.org/computing/computer-science/algorithms/binary-search/p/challenge-binary-search

任何帮助将不胜感激！谢谢！

编辑：我应该对此进行编辑以说明我从可汗学院收到的错误消息是“看起来您在 while 循环中几乎拥有正确的条件，但它仍然有问题。” 这不是非常有用。

/* Returns either the index of the location in the array,
  or -1 if the array did not contain the targetValue */
var doSearch = function(array, targetValue) {
	var min = 0;
	var max = array.length - 1;
    var guess;
    while(max > min) {
        guess = Math.floor((max+min)/2);
        if(array[guess] === targetValue) {
            return guess;
        } else if (array[guess] < targetValue) {
            min = guess + 1;
        } else {
            max = guess - 1; …

我们有 STL（标准模板库）多重集，我们想要实现一个二分搜索，它将为我们提供与某个值 x 相比的第一个小于或等于的元素

从这篇文章：lower_bound == upper_bound中，我们看到我们可以使用标准的 lower_bound 和 upper_bound 来找到比 x 更大的值，或者找到更小的或等于的值。

可以做这样的事吗？

说说Arrays中定义的这个方法：

public static int binarySearch(int[] a, int key)

我无法理解为什么返回(-(insertion point) - 1)而不是-(insertion point)在数组中找不到匹配项的情况。

https://docs.oracle.com/javase/7/docs/api/java/util/Arrays.html#binarySearch(int[],%20int)

这可能是Math.abs((-(insertion point) - 1))等于数组大小的原因吗？

如果你想知道我为什么要问这个问题，我看到为了找到插入点，我基本上必须做减法。

int returnedVal = Arrays.binarySearch(arr, needle);
if (returnedVal < 0) 
     insertionPoint = Math.abs(returnedVal) - 1; 

我决定将数组存储到二叉树中，以便数组的所有元素都位于树的右侧。如何计算所有这些元素？

int get_length(Node * array) {
   static int len = 0;
   if (array == NULL) return len;
   else {
       len++;
       get_length(array->right);
   }
}

静态变量问题：每次使用该函数后，变量len未复位，返回长度不正确。每次使用后，该变量都会增加。

测试用例超时。可能使用无限循环或低效算法。 参数无法更改，某些测试用例失败。我哪里出错了？

int binarySearch(int p[], int n, int key) {
    int l = 0, h = n - 1;
    int mid = l + (h - l) / 2;
    while (l <= h) {
        if (p[mid] == key) {
            return mid;
        }
        if (p[mid] < key) {
            l = mid + 1;
        }
        if (p[mid] > key) {
            h = mid - 1;
        }
    }
    return -1;
}

这是我的代码：

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;

class MyComp implements Comparator<String> {

    @Override
    public int compare(String o1, String o2) {
        return o1.compareTo(o2);
    }
    
}
public class CollectionsAlgo2 {

    public static void main(String[] args) {
        // Create an ArrayList
        ArrayList<String> al = new ArrayList<>();
        
        // Add elements to the array list.
        al.add("C");
        al.add("A");
        al.add("E");
        al.add("B");
        al.add("D");
        al.add("F");
        al.add(1, "A2");
        
        System.out.println("al: "+al);
        Collections.sort(al);
        System.out.println("al after sorting: "+al);
        int pos = Collections.binarySearch(al, "B", new MyComp());
        System.out.println("pos: "+pos);

    }

}

我的问题是在 Collections.binarySearch(List<? extends T> …

我知道二分搜索适用于排序数组，因为由于数组索引，可以在单位时间内访问中间元素。但在列表中，访问中间元素需要线性时间，使得二分搜索毫无意义。向量具有像列表一样灵活的大小，因此如果使用列表实现它们，则二分搜索不应该对它们起作用，对吗？或者向量是否使用具有动态内存分配的数组，并且在这种情况下二分搜索是否有效？（我是个初学者，逻辑上的错误还请大家指出）

我正在查看 Gosort包中的这个函数” func SearchInts(a []int, x int) int，并且好奇是否有一种直接的方法来识别切片中是否存在元素？

在 Java Arrays.binarySearch(..) 中，仅返回负值。我很好奇 golang 的 api 是否func SearchInts(a []int, x int)报告 x 不存在？不确定为什么func SearchInts(a []int, x int)不返回两个值(index,isPresent)？

我有一个看起来像的数组

2 6 8 5 34 1 12

我可以在某些子数组上使用二进制搜索吗？

在赋值时,我必须使用递归二进制搜索算法输出索引而不是True/False而不修改参数.我度过了一段非常艰难的时期,但在诉诸半试错之后,我偶然发现了这个烂摊子:

#include <iostream>
#include <math.h>
#include <climits>

using namespace std;


int BinarySearch(int arr[], int len, int target) {

    int temp = 0;
    int mid = len/2;

    if (len <= 0) return INT_MIN;  // not found
    if (target == arr[mid]){
        return mid; // found
    }

    if (target < arr[mid]){
        temp = BinarySearch(arr, mid, target);
    }

    else {
        temp = mid+1 + BinarySearch(arr+mid+1, len-mid-1, target);              
    }
}

即使在通过可视化工具运行之后,我也完全不知道它为什么会起作用.它对更改的代码非常敏感,当它无法找到目标时我无法输出-1,所以我至少总是输出一个负数.

我真的不需要它固定,我只是想知道它是如何工作的,因为看起来甚至没有使用递归调用的输出.谢谢.