有序数组有重复数，二分法怎么返回数组中所有的要查找的数的下标

s7703179

比如  int  a[10]={2,3,5,6,6,6,6,6,8,9}

用二分法，把所有6的下标得到，能实现吗？或者有其他算法 求指教

linux_c_py_php

lower_bound+upper_bound，实现这两种二分查找。

leejqy

int lowerBound (const int*pIArr, int start, int end, int val)
{
    int middle;
    while (start < end) {
        middle = (start + end) >> 1;
       if (!middle || (val == pIArr[middle] && pIArr[middle - 1] < val) return middle;
       else if (pIArr[middle] > val) end = middle - 1;
       else start = middle + 1;
    }
    return -1;//不存在
}
int upBound (const int *pIArr, int start, int end, int val)
{
    int middle;
    while (start < end) {
        middle = (start + end) >> 1;
       if (middle == end || (val == pIArr[middle] && pIArr[middle + 1] > val) return middle;
       else if (pIArr[middle] > val) end = middle - 1;
       else start = middle + 1;
    }
    return -1;//不存在
}

hellioncu

现用正常的二分找到一个，然后往两头找

leejqy

这样做可能蜕化成线性查找
回复 4# hellioncu


   

fender0107401

这个要看重复的次数多少了，如果重复的很少，那就找到一个然后往两边跑。

如果比较多，那就上最上面的和最下面的。

bruceteen

#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
    ///////////// 0 1 2 3 4 5 6 7 8 9
    int a[10] = { 2,3,5,6,6,6,6,6,8,9 };

    std::pair<int*,int*> r = std::equal_range( a+0, a+10, 6 );
    cout << '[' << (r.first-a) << ',' << (r.second-a) << ')' << endl; // output: [3,8)

    return 0;
}

yulihua49

mark ----

leejqy 发表于 2013-05-16 16:31
int lowerBound (const int*pIArr, int start, int end, int val)
{
    int middle;

yulihua49

yulihua49 发表于 2013-06-14 15:45
mark ----

做了一个实用化的，可以是任意结构数组，自定义key：

1. #include <Binary_search.h>
   
2. 
   
3. #include <Binary_search.h>
   
4. 
   
5. int lowerBound(void *key,void *data,int data_count,int (*compare)(void *key,void *data,int n))
   
6. {
   
7. int middle,start=0,end=data_count-1,val;
   
8.     while (start <= end) {
   
9.         middle = (start + end) >> 1;
   
10. //printf("lower:start=%d,end=%d,middle=%d\n",start,end,middle);
    
11.         val=compare(key,data,middle); //data - key
    
12.        if (!val && (!middle||compare(key,data,middle - 1) < 0)) return middle;
    
13.        else if (val>=0) end = middle - 1;
    
14.        else start = middle + 1;
    
15.     }
    
16.     return -1;//不存在
    
17. }
    
18. 
    
19. int upperBound(void *key,void *data,int data_count,int (*compare)(void *key,void *data,int n))
    
20. {
    
21. int middle,start=0,end=data_count-1,val;
    
22. int result=-1;
    
23. 
    
24.         if(!key||!data) return -1;
    
25.         while(start <= end) {
    
26.                 middle=(start+end+1)>>1;
    
27. //printf("upper:start=%d,end=%d,middle=%d,result=%d\n",start,end,middle,result);
    
28.                 val=compare(key,data,middle);
    
29.                 if(val>0)  {
    
30.                         if(!middle||compare(key,data,middle - 1) <= 0)
    
31.                                 result=middle;
    
32.                         end=middle-1;
    
33.                 } else {
    
34.                         start=middle+1;
    
35.                 }
    
36.         };
    
37.         return result;
    
38. }
    
39. /* UP=KEY
    
40. {
    
41. int middle,start=0,end=data_count-1,val;
    
42.     while (start <= end) {
    
43.         middle = (start + end+1) >> 1;
    
44. //printf("start=%d,end=%d,middle=%d\n",start,end,middle);
    
45.         val=compare(key,data,middle);//data - key
    
46.        if (!val &&  (middle==data_count-1||compare(key,data,middle + 1) > 0)) return middle;
    
47.        else if (val>0) end = middle ;
    
48.        else start = middle + 1;
    
49.     }
    
50.     return -1;//不存在
    
51. }
    
52. */
    

复制代码

upperBound（）进行了一点小调整，否则会有疏漏。

yulihua49

yulihua49 发表于 2013-06-18 12:30
做了一个实用化的，可以是任意结构数组，自定义key：upperBound（）进行了一点小调整，否则会有疏漏。

例子：

1. #include <stdio.h>
   
2. #include <Binary_search.h>
   
3. 
   
4. static int tab[]={-1,-1,0,1,1,1,1,2,2,2,2,3,3,4,5,5,5,5,5,5,6,6,6,7};
   
5. #define COUNT sizeof(tab)/sizeof(int)
   
6. 
   
7. static int int_cmp(void *key,void *data,int n)
   
8. {
   
9. int *d=(int *)data+n;
   
10.         return *d-*(int*)key;
    
11. }
    
12. 
    
13. int main(int argc,char *argv[])
    
14. {
    
15. int ret,low,up,key;
    
16. 
    
17.         key=7;
    
18.         low=lowerBound(&key,tab,COUNT,int_cmp);
    
19.         up=upperBound(&key,tab,COUNT,int_cmp);
    
20.         
    
21.         printf("key=%d,low=%d,up=%d\n",key,low,up);
    
22.         return 0;
    
23. }
    

复制代码

结果：
-bash-3.00$ ./tbound
key=7,low=23,up=23