标签: linear-search

线性搜索和二进制搜索有什么区别？

我正在寻找优化这种线性搜索:

static int
linear (const int *arr, int n, int key)
{
        int i = 0;
        while (i < n) {
                if (arr [i] >= key)
                        break;
                ++i;
        }
        return i;
}

数组已排序,函数应返回大于或等于键的第一个元素的索引.它们的数组不大(低于200个元素),并且会为大量搜索准备一次.如果需要,可以在第n个之后将数组元素初始化为适当的数组,如果这样可以加快搜索速度.

不,不允许二进制搜索,只能进行线性搜索.

编辑:我在博客文章中总结了有关此主题的所有知识.

这个问题是关于线性搜索的效率与连续存储中预排序数组的二进制搜索的效率...

我有一个用fortran编写的应用程序(77!).我的部分代码的一个常见操作是在数组中找到索引gx(i) <= xin < gx(i+1).我目前已经实现了这个binary search- 对于声明标签而言goto- 并且- 我已经评论了使用fortran 90的等效声明...

        i=1
        ih=nx/2
201     continue  !do while (.true.)
           if((xin.le.gx(i)).and.(xin.gt.gx(i+1)))then  !found what we want
              ilow=i+1; ihigh=i
              s1=(gx(ihigh)-xin)/(gx(ihigh)-gx(ilow))
              s2=1.0-s1
              return
           endif
           if(i.ge.ih)then
              goto 202 !exit
           endif
           if(xin.le.(gx(ih))then !xin is in second half of array
              i=ih
              ih=nx-(nx-ih)/2
           else !xin is in first half of array
              i=i+1
              ih=i+(ih-i)/2
           endif
        goto 201  !enddo

然而,今天,我正在维基百科上阅读二进制搜索,我发现了这个:

Binary search can interact poorly with the memory hierarchy 
(i.e. caching), because of its random-access …

我一直在寻找各种不同的搜索集合,集合集合等方式.我做了很多愚蠢的小测试来验证我的理解.这是令我高兴的一个(下面的源代码).

简而言之,我生成N个随机整数并将它们添加到列表中.该列表未排序.然后我Collections.contains()用来在列表中查找值.我故意寻找一个我知道不会存在的值,因为我想确保探测整个列表空间.我在这个搜索时间.

然后我手动执行另一个线性搜索,遍历列表的每个元素并检查它是否与我的目标匹配.我也是这次搜索的时候了.

平均而言,第二次搜索比第一次搜索长33%.根据我的逻辑,第一次搜索也必须是线性的,因为列表是未排序的.我能想到的唯一可能性(我立即丢弃)是Java正在为我的列表制作一个排序的副本,仅用于搜索,但(1)我没有授权使用内存空间和(2)我会认为如此大的N可以节省更多的时间.

因此,如果两个搜索都是线性的,那么它们都应该花费相同的时间.不知怎的,Collections类已经优化了这个搜索,但我无法弄清楚如何.那么......我错过了什么？

import java.util.*;

public class ListSearch {

    public static void main(String[] args) {

        int N = 10000000; // number of ints to add to the list
        int high = 100; // upper limit for random int generation

        List<Integer> ints;
        int target = -1; // target will not be found, forces search of entire list space

        long start;
        long end;

        ints = new ArrayList<Integer>();
        start = System.currentTimeMillis();
        System.out.print("Generating new list... ");
        for (int i = …

所以在我的程序中有一个if-else分支,大约有30个if-else语句.这部分每秒运行超过100次,因此我将其视为优化的机会,并使用函数指针数组(实际上是平衡树映射)进行二进制搜索,而不是进行线性if-else条件检查.但它的速度比以前的速度快了约70%.

我做了一个简单的基准测试程序来测试这个问题,它也给出了类似的结果,if-else部分运行得更快,无论是否有编译器优化.

我还计算了完成的比较次数,正如预期的那样,进行二进制搜索的人比简单的if-else分支做了大约一半的比较.但它仍然慢了20%~30%.

我想知道我的计算时间浪费在哪里,为什么线性if-else比对数二进制搜索运行得更快？

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

long long ifElseCount = 0;
long long binaryCount = 0;

int ifElseSearch(int i) {
    ++ifElseCount;
    if (i == 0) {
        return 0;
    }
    ++ifElseCount;
    if (i == 1) {
        return 1;
    }
    ++ifElseCount;
    if (i == 2) {
        return 2;
    }
    ++ifElseCount;
    if (i == 3) {
        return 3;
    }
    ++ifElseCount;
    if (i == 4) {
        return 4;
    }
    ++ifElseCount;
    if (i == 5) {
        return 5;
    }
    ++ifElseCount;
    if …

在互联网上搜索之后，我无法让自己满意，因为我发现了一组综合的情况，其中线性搜索比二分搜索更可取。

我基本上想知道是否有可能编制一份相对明确的建议清单（从人们在工业中可能会发现的一般编程的角度来看）。或者，如果可以证实我确实已经看到了有关该主题的所有内容，我将不胜感激。

我试图推导出确定性线性搜索算法的平均案例运行时间.该算法按照A [1],A [2],A [3] ...... A [n]的顺序搜索未排序数组A中的元素x.它在找到元素x时停止或继续直到它到达数组的末尾.我在维基百科上搜索,给出的答案是(n + 1)/(k + 1),其中k是数组中x的存在次数.我以另一种方式接近并得到了不同的答案.任何人都可以给我正确的证据,也让我知道我的方法有什么问题吗？

E(T)= 1*P(1) + 2*P(2) + 3*P(3) ....+ n*P(n) where P(i) is the probability that 
                   the algorithm runs for 'i' time (i.e. compares 'i' elements).
P(i)= (n-i)C(k-1) * (n-k)! / n! 
Here, (n-i)C(k-1) is (n-i) Choose (k-1). As the algorithm has reached the ith 
step, the rest of k-1 x's must be in the last n-i elements. Hence (n-i)C(k-i).
(n-k)! is the total number of ways of arranging …

我正在尝试使用SSE指令通过uint64数组实现线性搜索。我为uint16和uint32工作，但我得到uint64代码的编译器错误（linux，gcc-请参见最后的规格）。

我正在尝试比较2x2 64位数字，然后以某种方式将结果转换为数组的索引。这可以与uint32一起很好地工作（学分请访问 http://schani.wordpress.com/2010/04/30/linear-vs-binary-search/）：

#include <xmmintrin.h>
#include <smmintrin.h>

typedef ham_u64_t vec2uint64 __attribute__ ((vector_size (16)));
typedef ham_u32_t vec4uint32 __attribute__ ((vector_size (16)));
typedef float     vec4float  __attribute__ ((vector_size (16)));
typedef ham_u16_t vec8uint16 __attribute__ ((vector_size (16)));
typedef ham_u8_t  vec16uint8 __attribute__ ((vector_size (16)));

// ...

vec4uint32 v1 = _mm_loadu_si128((const __m128i *)&data[start + i + 0]);
vec4uint32 v2 = _mm_loadu_si128((const __m128i *)&data[start + i + 4]);
vec4uint32 v3 = _mm_loadu_si128((const __m128i *)&data[start + i + 8]);
vec4uint32 v4 = _mm_loadu_si128((const __m128i *)&data[start + i + …

请在下面找到我的代码以进行线性搜索。二元搜索功能给出了正确的输出。但是在进行压力测试后，我没有得到正确的线性搜索输出。当使用压力测试产生的相同输入（测试用例）实现相同的线性搜索代码时，代码会给出正确的输出。

int linear_search(const vector<int> &a, int x) 
{
  for (int i = 0; i < a.size(); ++i) 
  {
    if (a[i] == x)
    {
      return i;
    }
  }
  return -1;
}

主功能

int main() {
   while(true)
   {
     int n=5;
   vector<int> a(n);
   for (size_t i = 0; i < n; i++) {
     int b = rand() % 5 + 1;
     a.push_back(b);
   }
   for (size_t i = 0; i < n; i++) {
     std::cout<<a[i]<<" ";
   }
   std::cout<<"\n";
   int x = rand() % 10 …

这段代码来自 Geeks for Geeks Algorithms 部分，我不明白这部分

int n = sizeof(arr) / sizeof(arr[0]); 

在主函数中，特别是为什么使用 sizeof(arr[0]) 的除法会导致数组中实际元素数量的一半。希望有人可以向我解释这一点。

// C++ code to linearly search x in arr[]. If x 

// is present then return its location, otherwise 
// return -1 

#include <iostream> 
using namespace std; 

int search(int arr[], int n, int x) 
{ 
    int i; 
    for (i = 0; i < n; i++) 
        if (arr[i] == x) 
            return i; 
    return -1; 
} 

int main(void) 
{ 
    int arr[] = { 2, 3, 4, 10, …