标签: binary-search

您正在开发一个项目，并且注意到两个版本之间的性能有所下降。你有一个功能：

boolean worseCommit(int commit1, int commit2) 

运行性能测试，如果 commit2 比 commit1 差则返回 true，否则返回 false。

查找所有降低版本之间性能的错误提交。假设性能没有改善。

提交 ID：1, 2, 3, 4, 5, 6, 7, 8, 9

表现：10, 10, 10, 8, 8, 8, 5, 5, 5

输出4, 7

我在二分搜索实现上遇到了很多困难，尤其是

• 如何选择高和低（或r和l）
• while循环条件中是否添加等号
• 是否更新r=mid或r=mid-1

我试图实施upper_boundfrom STL，但无法得到正确的答案。这是我的代码。

#include<iostream>
#include<vector>
#include<climits>

using namespace std;

int main()
{
    int n;
    cin >> n;
    vector<int> a(n+2);
    // adding 0 in front to avoid out of bounds error 
    // when looking for a[m-1]
    a[0]=0;
    for(int i=1; i<=n; i++)
        cin >> a[i];
    // adding a big element at the end to return that index
    // when required element is greater than all elements
    a[n]=INT_MAX;

    // q …

我尝试使用二分搜索来查找整数的平方根，但有些我无法通过一些测试用例。

我能够传递 mySqrt(4) = 2，但无法传递 mySqrt(2147395599)

关于我搞砸的地方有什么想法吗？

public static int mySqrt(int x) {
        int left = 0;
        int right = x;

        if(x < 2){
            return x;
        }
        while(left < right){
            int mid = left + ((right - left) / 2);

            if(mid * mid == x){
                return mid;

            }
            else if(mid * mid < x){
                left = mid + 1;
            }
            else{
                right = mid; 
            }
        }
        return left - 1;
    }

列表已排序.

我有一个List,我想对它进行二分搜索.T有StartIndex,EndIndex等成员.

我可以使用StartIndex对列表进行二进制搜索,即:我为此实现了IComparable.

我需要稍微扭转一下如下:我想找到一个可能是OffBy一个小值的StartIndex.

例如:T.StartIndex = 100

如果输入为101且OffBy为1,则BinarySearch应返回此对象.

我怎样才能做到这一点？

顺便说一句,我想问一下如何用List的默认二元搜索方法.这就是我感兴趣的,对自定义二进制搜索实现不感兴趣.

我想制作一个通用的BST,它可以由任何数据类型组成,但是如果我的BST是通用的,我不知道如何向树中添加内容.我需要的所有代码都在下面.我希望我的BST由Locations组成,并按x变量排序.任何帮助表示赞赏.

非常感谢您的关注.

public void add(E element)
{
    if (root == null)
         root = element;
    if (element < root)
         add(element, root.leftChild);
    if (element > root)
         add(element, root.rightChild);
    else
         System.out.println("Element Already Exists");
}

private void add(E element, E currLoc)
{
    if (currLoc == null)
         currLoc = element;
    if (element < root)
         add(element, currLoc.leftChild);
    if (element > root)
         add(element, currLoc.rightChild);
    else
         System.out.println("Element Already Exists);
}

其他代码

public class BinaryNode<E>
{
    E BinaryNode;
    BinaryNode nextBinaryNode;
    BinaryNode prevBinaryNode;

    public BinaryNode()
    {
        BinaryNode = null;
        nextBinaryNode …

我有一个字符串数组,默认排序.我希望在java中对这个列表进行二进制搜索.java中的字符串是否有任何buit-in二进制搜索功能？

我正在用C++实现二进制搜索算法,但算法没有返回正确的值.代码可以在这里找到.

template<class T>
int binary_search(T search_value, T search_array[]) {

    int mid; /* The middle element of the remaining array to be searched. */
    int min = 0; /* The first index of the array. */
    /* This forumla gives us the size of the array. */
    int max = sizeof(search_array)/sizeof(search_array[0]);

    /* Continue searching until min >= max. */
    while (min < max) {
        /* Compute the value of mid using a formula that won't produce a number
         * …

嗨,

如果我们使用二进制搜索在以下数组中搜索24,那么搜索键的索引是什么.

array = [10,20,21,24,24,24,24,24,30,40,45]

我对二进制搜索有疑问,如果数组有重复值,它是如何工作的.任何人都可以澄清...

这是一个带有递归二进制搜索算法的C程序,但是当我运行它时,调试器说二进制搜索功能中存在访问分段错误.为什么这样,我该如何解决这个问题？

这是递归二进制搜索功能:

int binSearch(int val, int numbers[], int low, int high)                 
{
     int mid;

     mid=(low+high)/2;
     if(val==numbers[mid])
     {  
                return(mid);          
     }   
     else if(val<numbers[mid])
     {
                return(binSearch(val, numbers, low, mid-1));               
     }            
     else if(val>numbers[mid])
     { 
                return(binSearch(val, numbers, mid+1, high));  
     }    
     else if(low==high)
     {
                return(-1);    
     }
}

谢谢 :)

我的任务是完成对涉及简单C++编码练习的职位的技术评估.问题是检查排序数组中是否存在数字,其中:

• ints[] 是要排序的数组
• size 是数组的大小
• k 是要检查的号码

要求是实现尽可能少使用CPU周期的解决方案.我的解决方案如下:

static bool exists(int ints[], int size, int k)
{
    std::vector<int> v(ints,ints+size);

    if (std::binary_search (v.begin(), v.end(), k))
        return true;

    return false;
}

这在数组中有一百万个项目的性能测试失败了.我有点困惑为什么.我是从矢量创建一个新结构的事实吗？它是否涉及将所有项目复制到内存中的新位置？