标签: binary-search

我正在尝试使用Java API规范中记录的binarySearch方法,但我的IDE(Eclipse(Helios))无法识别签名.

我的课程归结为它的2个数据成员以及我试图调用Arrays.binarySearch的方法:

import java.util.Arrays; // Access Arrays class
public class SortedStringArrayList {
    // member data
    private String[] items;
    private int size;

    // methods
    public int testBinSearch(String item) {
        int index = Arrays.binarySearch(items, 0, size, item);
    }
}

当我在方法中编写代码时,Eclipse假定我想要一个不同的签名并告诉我:

Arrays类型中的方法binarySearch(int [],int)不适用于参数(String [],int,int,String)

它建议可用的binarySearch的签名是:

我是Java/Eclipse的新手.谁知道问题是什么？

while循环使用线性搜索向后扫描.但是,我们知道while循环中的数组已经排序.因此,我们可以用二进制搜索替换线性搜索,以便O(n)将变为O(lg n).但是,我对此的看法是它不会有助于减少总体时间,因为我们仍然需要将元素向前移动一个索引,这将始终采用(向后步骤数(n))次.总的来说,运行时间保持为O(n ^ 2),并且在这种情况下无法实现O(n lg n).如果我以错误的方式接近这个,请告诉我.

INSERTION-SORT(A)

 for j = 2 to length[A]
  do key = A[j]
     i = j - 1

  while i > 0 and A[i] > key
    A[i+1] = A[i]
    i = i - 1

  A[i+1] = key

我有一个建立在ASP.net MVC3上的电子商务网站.它有appx.200k产品.我们目前正在产品表中搜索,以便在网站上提供搜索.

问题是这是致命的慢,当然,通过分析探查器的性能我们发现它是sql搜索,这是主要问题.

有哪些其他替代方案可用于加速搜索？我们是否需要为搜索构建单独的缓存或者还需要做任何其他事情？

如果你看看其他大型电子商务网站,如ebay,amazon或flipkart,它们非常快.他们是如何做到的呢？

我有一些很好的突破,了解一些更先进的排序,选择,搜索等算法.

这是我坚持的情景.

对于要在其中找到第k个最小元素的值数组,可以使用quickselect(如果未排序)和二进制搜索(如果已排序).

如果我理解正确,通过数据透视/分区系统,quickselect将通过选择一个数据集来搜索未排序的数据集,通过将每个元素与数据透视表进行比较来创建低点和高点组,然后通过更改将列表递归地分解为子列表枢.

这听起来与二进制搜索的工作方式非常相似,那么为什么quickselect对未排序的值起作用而二进制搜索不起作用,并且并不是所有的快速选择算法(计算出低点和高点)的比较都需要很多......成本？

我编写了以下程序来实现已排序数组的二进制搜索:

    int flag=0;

    void binarysearch(int x, int a[], int m, int n)
    {
        int middle=(m+n)/2;
        if(a[middle]==x)
        {
            printf("%d has been found at postion %d!\n", x, middle+1);
            flag=1;
        }
        else
        if(x > a[middle])
            binarysearch(x, a, middle, n);
        else
        if(x < a[middle])
            binarysearch(x, a, m, middle);
    }

    main()
    {
        int i, size, x;
        int a[100];
        printf("Enter the size of the list : ");
        scanf("%d", &size);
        printf("Enter the list items in ascending order : \n");
        for (i=0; i<size; i++)
        scanf("%d", &a[i]);
        printf("Enter the …

我想从用户获取用户输入并进行非递归二进制搜索可以任何人告诉我如何做它会不胜感激

public class Main {
// binarySeach: non-recursive
   public int Main(int[] a, int x) {
      int low = 0;
  int high = a.length - 1;
  while (low <= high) {
     int mid = (low + high)/2;
     if (a[mid] == x) return mid;
     else if (a[mid] < x) low = mid + 1;
     else high = mid - 1;
  }
  return -1;
  }



 public static void main(String[] args) {
      Main bin = new Main();
  int[] a =
    { 2, 8,12,14,16,19,24,28,31,33,// 0-9 …

我试图写一个我以前从未做过的"二分搜索".当搜索的值为6或2时,下面的代码不起作用,我想知道我做错了什么以及如何解决它.

编辑

为了解释它的作用(根据我的理解),二进制搜索要求数组已经排序,然后查找数组的中点索引.例如,如果一个数组有九个索引(0-8),则中间点将是索引4.

var arr = [1, 2, 3, 4, 5, 6, 7, 8, 9];

然后,算法确定该中点的值是否高于或低于您要搜索的数字.数组一侧的所有元素都不包含搜索到的数字,并且在中点值之前存在的元素只是被删除.如果搜索值为8,则结果为:

[ 1, 2, 3, 4, 5, 6, 7, 8, 9 ]
array midpoint value: 5
[ 5, 6, 7, 8, 9 ]
array midpoint value: 7
[ 7, 8, 9 ]
array midpoint value: 8

码

//_________________________________________________BEGIN notes

    // Step 1. Get length of array 
    // Step 2. Find mid point
    // Step 3. Compare if mid point is lower or higher than searched …

我有一个向量pairs。假设是这样的：

vector<pair<int,int>> vec = { {1,12}, {1,5}, {1,6}, {1,9}, {3,9}, {3,11}, {3,13}, {3,4}, {5,9}, {5,91}, {13,8}, {16,8}, {20,8}, {20,81} };

在pairs由第一个元素进行排序。

给定a pair，我需要找到pair向量中最后一个元素的索引，该向量的第一个元素小于或等于给定对的第一个元素。如果对于最后一个pair，其他对以第一个元素的相同值位于其左侧，那么我需要所有这些对中的第一个：

<4,10> => 4 (vec[4] is <3,9>, the elements with the largest first value less than or equal to 4 are those with first element as 3, and there are 4 pairs with a 3 in the first element, at indices 4-7, so return the first of those pairs) …

我创建了一个列表，其中保存了一些字符串。但是，当我做二进制搜索这个列表中，它返回负值，而该项目是在列表中。

到目前为止，当列表中的项目返回时，我的知识肯定值将返回。但是对于某些项目，它返回负数，对于某些项目，它返回正数。

@Test
public void hello()
{
//  List<String> arlst = new ArrayList<String>();
    List arlst = new ArrayList();
    arlst.add("TP");
    arlst.add("PROVIDES");
    arlst.add("QUALITY");
    arlst.add("TUTORIALS");
    arlst.add("Stop");
    arlst.add("StopP");
    for (Iterator<String> iterator = (Iterator<String>) arlst.iterator();
            iterator.hasNext();)
    {
        Object next = iterator.next();
        System.out.println("next : " + next + " >> Search result : "
            + Collections.binarySearch(arlst, next.toString()));
    }

}

next : TP >> Search result : -7
next : PROVIDES >> Search result : …