标签: binary-search

我做了一些研究，但找不到任何东西，但如果这是重复的，请告诉我。

我有这段代码用于整数的二分搜索

package thepac;

public class CustomBS{

public static void main(String[] args){
    int[] listOfNumbers = new int[]{2,45,65,76,89,100,342,455};
    int numberToSearch = 100;
    int lowestIndex = 0;
    int highestIndex = listOfNumbers.length-1;
    int middleIndex;

    while(lowestIndex<=highestIndex){
        middleIndex = (lowestIndex+highestIndex)/2;

        if(numberToSearch > listOfNumbers[middleIndex]){
            lowestIndex = middleIndex+1;
        }else if(numberToSearch < listOfNumbers[middleIndex]){
            highestIndex = middleIndex-1;
        }else{
            break;
        }
    }//end of while
    if(lowestIndex > highestIndex){
        System.out.println("not found");
    }else{
        System.out.println("found");
    }
}
}

这只是找到并且我理解这个概念。是否可以实现一个在字符串数组中搜索字符串的版本？

我想不出如何实现这一点，因为当前的算法检查正在搜索的数字是否高于或低于中间索引，但如果它是一个字符串，我如何检查它是否高于或低于另一个字符串？

我知道我可以使用 String.compareTo() 方法来检查一个字符串是否比另一个字符串更大或更短，但我不确定这是否是实现此目的的正确方法。

以下代码应该对卡片数组中的卡片进行递归二分搜索。Eclipse 给出一个错误，指出该方法不返回整数。

public static int binaryrSearch(Card[] cards, Card target , int low , int high)
{
    if (high<low)
    {
        return -1;
    }
    int mid = (low+high)/2;
    int comp = cards[mid].compareTo(target);
    if(comp==0)
    {
        return mid;
    }else if(comp<0)
    {
        return binaryrSearch(cards , target , mid+1 , high);
    }else if (comp>0)
    {
        return binaryrSearch(cards , target , low , mid-1);
    }
}

比较方法：

public int compareTo(Card that){
    if(this.suit<that.suit)
    {
        return -1;
    }
    if(this.suit>that.suit)
    {
        return 1;
    }
    if(this.rank<that.rank)
    {
        return -1;
    }
    if(this.rank>that.rank) …

我一直在 Coursera 上学习 DSA 课程，本周介绍了搜索算法。而二分查找的复杂度(O(logn))优于线性查找(O(n))。但是，考虑到首先需要 nlogn 工作才能对数组进行排序，为什么我要在未排序的数组中使用它呢？

如果二分搜索仅在数组已排序的情况下使用，那么为什么要如此频繁地比较这两种算法，因为显然它们有不同的用例。

我正在阅读 USACO Silver 上有关排序集的指南，我遇到了这个警告（s是std::set整数）：

警告！
假设我们替换s.upper_bound(7)为upper_bound(begin(s),end(s),7)，这是我们在先决条件模块中用于向量的语法。这仍然会输出预期的结果，但它的时间复杂度与集合的大小是线性的s，而不是对数的，所以一定要避免它！

他们的意思是什么 ？

   upper_bound(s.begin(), s.end(), 7 ); // O(n) ?
   s.upper_bound(7);                    // O(log N) ?

我想编写一个二分搜索函数，它将指向数组的指针作为输入并查找可搜索元素的索引。

uint8_t binary_search(uint8_t * array, uint8_t element);

但我想传递给这个函数的数组有不同的类型（无符号8位，无符号16位，有符号8位等）

我正在考虑一种方法，可以将数组作为空指针传递，然后根据大小对其进行类型转换，但我无法找到正确的方法来实现它。

uint8_t binary_search(void * array, uint8_t element)
{
  if(sizeof(array[0] == 1)
  {
  }
  else if
  .
  .
  .
}

最后一个选项是将多个数组传递给函数并再次根据大小进行选择，但我希望是否有更好的方法来处理这种情况。

任何帮助表示赞赏。谢谢！

我有字符串数组[1,2,3],我使用Arrays.binarySearch搜索所有这些数字,它找到1和2,但是3,它返回-1.任何想法为什么它这样工作？什么是总是在数组/集合中搜索的更好的替代方案？

以下代码有什么问题？怎么没有找到使用我的二进制搜索实现的信？

#include <iostream>
#include <string>
#include <algorithm>
#include <cctype>
#include <cwctype>
using namespace std;

bool contains(string s, char a){
  int m = 0;
  int n = s.length()-1;

  while (m != n) {
    int k = (m + n) / 2;
    if (s[k] == a)
      return true;

    if (s[k] < a) {
      n = k - 1;
    } else {
      m=k + 1;
    }
  }

  return false;
}

int main() {

  string s = "miyvarxarmaiko";
  char a = 'm';
  if (contains(s,a) …

我有一个列表,其中包含所有元素作为表单的结构

typedef struct person_node{
    string name;
    string country;
}person;

std::list<person> list;

该列表已按人名排序.

我如何使用内置的binary_search()函数？

我已经知道如何在列表中使用这个binary_search()只有数字作为数据,但我想知道如何将它用于这样的列表.

我使用这个二进制函数:

binary_search (list.begin(), list.end(), value, compare_function);

我唯一不知道的是," 如果我需要在列表中查找特定名称,我应该输入什么来代替价值？"

我还想要一个迭代器指向该节点,如果找到的话.

我想在排序的向量V上对c ++执行二进制搜索.特别是,我对找到向量条目的确切值不感兴趣.我想找到满足V [j-1] <= X <V [j]的条目的位置j,其中X是输入值.

例如:对于向量v = {1,4,7,12,17,55}和X = 8,函数应返回3.

我可以使用具有O(log(2))复杂度的STD函数binary_search吗？

如何？

非常感谢,

人.

我有一张数据图；关键是std::string。我想对它执行二进制搜索，但是我不能只使用std::map::find()，因为我将只提供一部分密钥。

假设我有一张带有以下按键的地图：

["abc"] -> ...
["efg"] -> ...
["ijk"] -> ...
["iik"] -> ...

我想使用进行搜索，比如说仅提供"i"，搜索应该返回：

[“ ijk”]-> ...，[“ iik”]-> ...

这可能吗？我尝试使用迭代器来执行此操作，但由于无法将它们视为索引而失败了。

注意：由于其他原因，我将数据保留在地图中，所以我不想将其更改为其他数据结构。