标签: binary-search

第2列("AHA!算法")中的"编程珍珠"讨论了二进制搜索如何帮助各种过程,如排序,树遍历.但它提到二进制搜索可以用于"程序调试".有人可以解释一下这是怎么做的吗？

这个程序要求我:编写一个与用户进行简单数字猜测的程序.用户想到一个数字,然后回答计算机询问的一系列问题,直到它正确猜出数字为止.

我的问题是编译器说:'arr'未声明(首次在此函数中使用)

到目前为止,这是我的代码:

#include <stdio.h>
#include "strlib.h"
#include "simpio.h"

#define size 200

int binSearch (int num);
void getArray (int arr[]);

main()
{
      printf("Think of a number in the range of 1-200 and I'll guess it.\n");
      int arr[size];
      getArray(arr);
      binSearch(arr);
      getchar();
}

void getArray (int numbers[])
{
      int number;

      for(number=1;number>=200;number++)
      {
                 arr[number]=number;                                 
      }    
}

int binSearch(int num)
{
      int low, high, mid;
      string strReply;

      low=0;
      high=size-1;

      while(low<=high);
      {
                 mid=low+high/2;
                 printf("\nIs the number %d ?\t", mid);
                 strReply= GetLine();
                 if(StringEqual(strReply, "no")) …

我正在尝试在F#中实现一个简单的二进制搜索,作为学习函数式编程的一种方式.我已经在C#中以强制方式实现了它,这是我的主要语言,但我认为通过在F#中以递归的方式实现它来学习函数概念是一个很好的挑战.我已经足够远,它正确地找到了值,我的问题是我希望函数返回-1,如果值不在数组中,否则值的索引,但我无法想出跟踪指数的好方法.这是我的代码:

let rec chop i (nums:array<int>) =
match nums with
| [||] -> -1
| [|x|] -> if x = i then x else -1
| _ -> 
    let mid = nums.Length / 2 in
    if nums.[mid] < i then (chop i nums.[mid..])
    elif nums.[mid] > i then (chop i nums.[..mid])
    else mid

[<EntryPoint>]
let main argv = 
    printfn "%d" (chop 20 (Array.init 100 (fun index -> index * 2)))
    System.Console.ReadKey() |> ignore
    0 // return an integer exit code …

我有一个排序的日期列表,我正在寻找一种方法来查找输入日期在该排序列表中的位置,但更具体地说是它的上限.

例如,如果在排序日期列表中定位它[0, 1, 2, 3, 4, 5],然后输入日期在位置3和4之间,我希望函数将位置4返回给我.

我可以使用预先制作的二分搜索等吗？或者我必须自己写吗？

所以我正在搜索一个巨大的ArrayList以查找特定的String值，但是如果我要查找的String与我传入的String相等（不区分大小写），则需要Collections.binarySearch（）返回> = 0的值。 binarySearch（）方法。

现在，在Collections.binarySearch（）的源代码中，它最终将调用以下代码行。

 Comparable<? super T> midVal = list.get(mid);
 int cmp = midVal.compareTo(key);

如此看来，我无法覆盖String作为其最终值（因此防止我覆盖其compareTo（）方法以调用compareToIgnoreCase（）），还有其他方法可以实现吗？

任何帮助将非常感谢。

我正在使用 c# WPF 来开发 Windows 应用程序。应用程序需要一个类如下

public class Limits
{

    public String col1
    {
        get;
        set;
    }


    public String col2
    {
        get;
        set;
    }

    public String col3
    {
        get;
        set;
    }
}

我正在使用列表来存储对象，例如：-

List myList<Limits> = new List<Limits>();

“myList”有大约 15000 个对象。

现在，我想在此 myList 中搜索特定属性。例如：我想找出 col1 设置为“abc”的对象。

我如何使用二分搜索来解决这个问题？

大概做错了什么？尝试使用二进制搜索从数组中删除类中的实例.实例在创建时添加到数组中,但是当我从场景中删除它时,我希望它们也从数组中删除.以某种方式,binary_search在第一次删除时工作正常,但在删除第二个实例时却没有.

如果在数组中找到实例,binary_search应该返回true.但是当实例肯定存在于数组中时,它返回false.

这是我正在使用的代码.

void Manager::eraseInstance(SomeInstance* instance) {
    cout<< " found?: " << binary_search(instanceArray.begin(), instanceArray.end(), instance) << "  instance:  " << instance;
    for (int i = 0; i < instanceArray.size(); i++) {
        cout << "  " << i << ":  " << instanceArray[i];
    }
    cout << endl;
    if (binary_search(instanceArray.begin(), instanceArray.end(), instance)) {
        for (int i = 0; i < instanceArray.size(); i++) {
            if (instanceArray[i] == instance) {
                instanceArray.erase(instanceArray.begin() + (i));
                delete instance;
            }
        }
    }
}

对于调试我首先cout搜索结果,然后我尝试擦除的实例,然后是阵列中存在的所有实例.

现在我在控制台中的输出如下:

删除第一个实例输出:

发现?: 1实例:05DCB358 …

我在使用 STL 下限函数时遇到了一些问题。我是 C++ 的新手。我需要对 Biz 类的对象向量进行排序，所以我使用了这种排序：

bool cmpID(const Biz & a, const Biz & b) {
    return a.bizTaxID < b.bizTaxID; 
}
sort(bussiness_list.begin(), bussiness_list.end(), cmpID);

问题是当我尝试bizTaxID在另一个具有 lower_bound 的函数中找到一个对象 Biz by时。我以为我可以cmpID为此使用相同的功能，但显然不是：

taxID = itax; //function parameter, I am searching for the `Biz` with this ID
auto it = lower_bound(bussiness_list.begin(), bussiness_list.end(), taxID, cmpID);

我收到编译器错误：'bool (const Biz &,const Biz &)': 无法将参数 2 从 'const std::string' 转换为 'const Biz &'

我想我可以使用相同的比较功能进行搜索和排序。有人可以向我解释错误在哪里，究竟lower_bound需要我传递什么？正如我所说，我是 C++ 的新手。

先感谢您。

为什么我的算法返回“-1”意味着目标值 73 不在数组中？（当显然 73 在数组中时）。[这是来自可汗学院，但没有帮助]

它应该返回数组中位置的索引，或者如果数组不包含 targetValue 则返回“-1”

Var doSearch = function(array, targetValue) {
    var min = 0;
    var max = array.length - 1;
    var guess;
    while(max >= min) {
        guess = floor((max*1 + min*1) / 2);
        if (guess === targetValue) {
            return guess;
        } else if (guess < targetValue) {
            min = guess + 1;
        } else {
            max = guess - 1;
        }
    }
    return -1;
};

var primes = [2, 3, 5, 7, 11, 13, 17, 19, …

从网上看，我了解到lower_bound()C++中的方法是用来返回一个迭代器，该迭代器指向范围[first, last)中的第一个元素，该元素的值不小于value。这意味着该函数返回下一个刚好大于该数字的最小数字的索引。

所以，对于下面给定的代码，我理解输出是 3。但是，因为有 6 的重复。如何使用lower_bound(). 我可以binary_search()为此实现我自己的，但我想知道如何通过lower_bound().

#include <iostream> 
#include <algorithm>
#include <vector> 

using namespace std; 

int main () 
{ 
    int array[] = {5,6,7,7,6,5,5,6}; 

    vector<int> v(array,array+8); // 5 6 7 7 6 5 5 6 

    sort (v.begin(), v.end()); // 5 5 5 6 6 6 7 7 

    vector<int>::iterator lower,upper; 
    lower = lower_bound (v.begin(), v.end(), 6); 
    upper = upper_bound (v.begin(), v.end(), 6); 

    cout << "lower_bound for 6 at position " << (lower- v.begin()) …