标签: binary-search

我想找到正弦函数的零点.参数是区间[a,b].我必须与二进制搜索类似.

实现一个在a和b之间的间隔中搜索窦函数中的空点的函数.搜索间隔[下限,上限]应减半,直到下限和上限彼此小于0.0001.

这是我的代码:

public class Aufg3 {
    public static void main(String[] args) {

        System.out.println(zeropoint(5,8));
    }

    private static double zeropoint(double a, double b){
        double middle = (a + b)/2;

        if(Math.sin(middle) < 0){
            return zeropoint(a,middle);
        }else if(Math.sin(middle) > 0){
            return zeropoint(middle,b);
        }else{
            return middle;
        }       
    }
}

它在返回零点(中间,b)的行上给了我很多错误;

在第一步中,我想找到间隔中的第一个零点.

有任何想法吗？

我在我的程序中实现了二进制搜索,但由于某种原因,它完全忽略了我的一个返回语句.有关的退货声明如下:return array[mid];

当我使用Eclipse的调试器时,我可以看到它进入if语句,运行return,然后它跳到以下两行:binarySearch(array, key, low, mid - 1);,return null;.

知道为什么会这样吗？

public Entry<K, V> binarySearch(Entry<K,V>[] array, K key, int low, int high) {
    if(low >= high) {
        Entry<K,V> notFound = new EntryNode<K,V>(null, null);
        return notFound;
    } else {
        int mid = (low + high) / 2;
        if(key.equals(array[mid].getKey()))
            return array[mid];
        else if(comparator.compare(key, array[mid].getKey()) < 0)
            binarySearch(array, key, low, mid - 1);
        else
            binarySearch(array, key, mid + 1, high);
    }   //End else statement
    return null;
}   //End binarySearch …

我有一个完全排序的2D数组.下面的数组是示例

    1  2  3  
    5  6  7  
    9 10 11 

和

    1  2  3  4  5
    6  7  8  9  10

我想在这些数组上使用二进制搜索.我们rows是行数和cols被列数

最初start = 0和end = rows * cols -1

在上面的3 X 3阵列中,中点可以是4 [9个元素].现在我如何找到具有中点的相应行和列？那有什么标准配方吗？

我注意到我的变量input2只打印字符串中的第一个单词,这导致程序其余部分出现问题(即不能正确打印名词).任何关于为什么会发生这种情况的见解将不胜感激

int main(int argc, char* argv[]){

    char *input = strtok(argv[1], " \"\n");
    //printf("%s\n", input);
    int position;
    int check = 0;
    int first = 1;
    while (input != NULL) {
        position = binary_search(verbs, VERBS, input);
        //printf("%s\n", input);
        //printf("%d\n", position);
        if (position != -1){
            if (first){
                printf("The verbs were:");
                first = 0;
                check = 1;
            }
            printf(" %s", input);
        }
        input = strtok(NULL, " ");
    }
    if (check == 1){
        printf(".\n");
    }
    if (check == 0){
        printf("There were no verbs!\n");
    }

    char …

怎么可能当我在SortedList上使用.net BinarySearch时,它需要的时间比我在同一个列表上使用我自己的二进制搜索方法要长得多？

使用.net binarysearch:

int ipos = MyList.Keys.ToList().BinarySearch(unSearchFor);

if (ipos >= 0)
{
    // exact target found at position "ipos"
    return MyList[unSearchFor];
}
else
{
    // Exact key not found: 
    // BinarySearch returns negative when the exact target is not found,
    // which is the bitwise complement of the next index in the list larger than the target.
    ipos = ~ipos;
    try
    {
        return MyList.Values[ipos - 1];
    }
    catch
    {
        return null;
    }
}

我的二元搜索方法:

int nStart = 0;
int …

我已经看到很多搜索算法要在二进制排序树中搜索,但它们都使用相同的方式:递归.我知道递归是昂贵相比,循环,因为每次我们调用了搜索功能,对于那些方法,它最终会使用大量的内存,如果二叉搜索树太大创建一个新的堆栈帧.

为什么我们不能像这样搜索二叉搜索树:

while (root!=NULL)
{
    if (root->data==data)
        return 0;
    else if (data > root->data)
        root=root->right;
    else
        root=root->left;
}

我认为这种方式比递归方式更快更有效,如果我错了,请纠正我!

你们都知道梯子和鸡蛋的问题,你需要找到一个最高的梯级,一个掉落的鸡蛋不会破碎.

有关100个梯级和2个鸡蛋的情况下堆栈溢出问题的解释,但是当你有一个无限的梯子时怎么样？(当然还有无限数量的鸡蛋)

在这种情况下你会如何处理这个问题？Fibonacci是否会搜索解决方案？

非常感谢您的帮助!

我知道Go有一个sort包含搜索功能的包,但这是出于教育目的.我一直在尝试在Go中实现二进制搜索算法,但我无法让它工作.

这是我的代码:

package main

import "fmt"

func BinarySearch(data []int, target int, low int, high int) (index int, found bool)  {
    mid := (high + low) / 2
    if low > high {
       index = -1
       found = false
    } else {
        if target < data[mid] {
            BinarySearch(data, target, low, mid - 1)
        } else if target > data[mid] {
            BinarySearch(data, target, mid + 1, high)
        } else if target == data[mid] {
           index = mid
           found = true …

试图为反向数组输入实现二进制算法.当我执行测试用例时 - 5 4 3 2 1它向我显示一个空白屏幕,即while循环无限运行.随时调试它,但无法弄清楚我哪里出错了.

#include <stdio.h>
#include <stdlib.h>

int findright(int arr[], int key, int low, int high);

void main() {
  int n, i, arr[200], key;
  scanf("%d %d\n", &n, &key);
  for (int i = 0; i < n; i++) {
    scanf("%d", &arr[i]);
  }
  int a = findright(arr, key, 1, n - 1);
  printf("%d", a);
}

int findright(int arr[], int key, int low, int high) {

  int mid = (low + high) / 2;
  while (low <= high) { …

我在C语言上尝试了这种(二分搜索)算法,其功能是在短时间内从一堆数字中找到一个数字.这是一种非常流行的技术.您也可以在Google上阅读相关内容.对我来说,它不适用于54和35,即最后两个数组.每当我想要搜索这两个数字时,它会显示"找不到项目".对于其余的数字,即前4个数组的数组,它工作正常.

#include <stdio.h>
#include <math.h>
int main(void)
{
    int item,beg=0,end=6,mid,a[6]={10,21,32,43,54,35};
    mid=(beg+end)/2;
    mid=round(mid);
    printf("Enter the number you want to search: ");
    scanf("%d", &item);
    printf("Item you entered is %d\n",item);
    while((a[mid]!=item) & (beg<=end))
    {
        if (item<a[mid])
            end=mid-1;
        else
            beg=mid+1;
        mid=(beg+end)/2;
        mid=round(mid);
    }

    if (item==a[mid])
        printf("Your number is at location %d in array and the number is %d",mid,a[mid]);
    else
        printf("Item not found");
    return 0;
}