位图算法－找中值

//
// Sample for vector arithmetic
// Write by spark

//

#include <stdio.h>

int arr[] = {1,3,5,7,9,2,4,6,8};           

#define MAX_NUM             (9)             //arr[]中的最大数
#define MIN_NUM             (1)             //arr[]中的最小数
                                                  //为了构建位图使用

#define ARR_MAX_INDEX       (sizeof(arr)/sizeof(arr[0]))   //arr[]中元素个数
#define VEC_MAX_INDEX       ((MAX_NUM)+1)                  //创建0~MAX_NUM的位图，这里可以优化，改为创
                                                                   //建MIN_NUM~MAX_NUM的位图,以节省空间。


int main(int argc, char *argv[])
{
    int vector_flag[VEC_MAX_INDEX] = {0};      //这里很浪费空间。:)
                                               //对空间有限制的话可以把32个flag压缩到一个int里
    int i, j, k;
    int middle_index;

    // set flag
    for (i=0; i<ARR_MAX_INDEX; i++)
    {
        vector_flag[arr[i]] = 1;
    }
  
    // search middle
    middle_index = (ARR_MAX_INDEX+1) / 2;       //注:这里假设arr[]中没有重复的值，否则要改
                                                       //变middle_index的算法。
    i=MIN_NUM-1; j=0;
    while(j<middle_index && i<VEC_MAX_INDEX)
    {
        i++;
        if (vector_flag[i]==1)
        {
            j++;
        }
    }

    // print result
    printf("middle number is : %d", i);

    return 0;
}