二进制搜索，以确定在哪里放置值

-1

我正在写C++代码来实现使用各种技术（数组，二叉树等）的哈希映射。我被卡在实现数组。我需要一种方法来确定放置新哈希的位置，以便数组在放置后进行排序。我的想法是使用二进制搜索来确定放置新散列的索引，然后推送所有其他元素。二进制搜索，以确定在哪里放置值

我遇到了该功能的问题。它应该有一定的原型是这样的：

int WhereToPlaceHash(HashType hash); // uses private atribute ValueType** values

我已经尽了全力来写这个功能，但所有我的尝试导致无限循环和阅读从数组无效的位置。请帮忙。

来源

2013-12-09 user3084657

我无法理解你的问题，在哈希表中，你不需要“搜索”一个值，你只需使用一些哈希函数来计算索引，然后模数组的大小，并且值应该是那里。如果两个值散列到同一个索引，则可以在该索引中放置链接列表。 – OopsUser

我还没有使用任何散列函数。只是简单的索引搜索。问题实际上是如何确定将新值放入排序数组中的位置（使用bin-search）。 – user3084657

如果您在编写此功能时包含了迄今为止最好的尝试，那么我们就会更容易了解您当前的思路。 – seaotternerd

通常，散列用作数组中的索引。另外，当使用散列时，你可能会得到一个按散列值排序但不是按键的数组（虽然这很明显）。如果你真的想找到其中的关键应在排序后的数组去的位置，你会使用std::lower_bound()：

int* pos = std::lower_bound(array, array + array_size, key);

返回迭代器pos将在第一位置，使得!(key < *pos)点。

来源

2013-12-09 22:23:19

要实现一个设置不同的实现类型

地图包含键和值对 - 你只需要一个键 - 所以它是一个设置

哈希手段一个不同的东西 - 它们是无序的，并且使用散列函数为所有具有相同散列项的列表选择一个桶，称为冲突（某些变体使用其他方案来处理冲突）。这是implented在STL为std::unordered_set，std::unsordered_map，...

对于排序使用的是保存在排序的数组的数组的数组实现，然后做有转移的所有项目更大，以保持插入排序。然后，您的查找将执行二分查找

插入将使用二进制搜索来查找放置项目的位置，然后移动大于它的所有项目。

的二进制搜索，开始在中间，然后repetively检查（低+中）/ 2，如果低于或（MID +最高）/ 2，如果更大，直到位置被发现

注意你将有什么区别之间发现没有找到

int binsearch(int * array, int len, int value, bool * found) 
{ 
    // return lowest position greater or equal to value 

    int lowp=0; 
    int highp=len-1; 
    int midp=(lowp+highp)/2; 

    while (lowp <=highp) 
    { 
     int mid=array[midp]; 
     if (mid > value) 
     { 
      highp=midp-1; 
     } 
     else if (value==mid) 
     { 
      *found=true; 
      return midp; // found at this position 
     } 
     else 
     { 
      lowp=midp+1; 
     } 
     midp=(lowp+highp)/2; 
    } 
    *found=false; 
    if (array[midp] > value) 
    { 
     return midp; // only at position 0 for a head insert 
    } 
    return midp+1; // not found - position to start shift 
} 

int main(int, char**) 
{ 
    int array[]={2,4,6,8,10,12,14,16,18,20}; 

    bool found; 

    for (int search=1; search < 22; ++search) 
    { 
     int a=binsearch(array, 10, search, &found); 

     std::cout << search << " at " << a << ":" << found << std::endl; 
    } 

    return 0; 
}

来源

2013-12-09 22:24:55

问题实际上是如何确定将新值放入排序数组中的位置（使用bin-search）。对不起，我很遗憾。 – user3084657

@ user3084657代码和测试主要添加到帖子 –

认真阅读本： binary search wiki

，并尝试这样的事：

int WhereToPlaceHash(int hash) { 
    int imin = 0, imax = YourSizeOfArray; 
    int imid = 0; 

    while (imax >= imin) { 
     imid = (imax + imin)/2; 

     if(YourArray[imid] == hash) 
     return imid + 1; 
     else if (YourArray[imid] < hash) 
     break; 
     else   
     imax = imid - 1; 
    } 

    return imid; 
}

来源

2013-12-09 22:49:10 Dumbledore

二进制搜索，以确定在哪里放置值

回答

相关问题