使用pthread进行二进制搜索-yiteyi-C++库

二进制搜索 是在排序数组或列表中搜索的常用方法。它简单地将列表分成两半，并丢弃拥有密钥的概率为零的那一半。在分割时，我们检查键的中点，如果键小于中点，则使用下半部分，如果键大于中点，则使用上半部分。二进制搜索的时间复杂度为O（log（n））。

null

二进制搜索也可以使用 多执行绪 我们利用处理器的内核，为每个线程提供一部分列表来搜索密钥。

线程数量取决于处理器的内核数量，最好为每个内核创建一个线程。

例如：

Input :  list = 1, 5, 7, 10, 12, 14, 15, 18, 20, 22, 25, 27, 30, 64, 110, 220
         key = 7
Output : 7 found in list

Input :  list = 1, 5, 7, 10, 12, 14, 15, 18, 20, 22, 25, 27, 30, 64, 110, 220
         key = 111
Output : 111 not found in list

推荐：请尝试你的方法 {IDE} 首先，在进入解决方案之前。

注—— 建议在基于Linux的系统中执行该程序。使用以下代码在linux中编译：

g++ -pthread program_name.cpp

                     // CPP Program to perform binary search using pthreads                   
                     #include <iostream>                   
                     using                               namespace                               std;                   
                             
                     // size of array                   
                     #define MAX 16                   
                             
                     // maximum number of threads                   
                     #define MAX_THREAD 4                   
                             
                     // array to be searched                   
                     int                               a[] = { 1, 5, 7, 10, 12, 14, 15, 18, 20, 22, 25, 27, 30, 64, 110, 220 };                   
                             
                     // key that needs to be searched                   
                     int                               key = 110;                   
                     bool                               found =                               false                               ;                   
                     int                               part = 0;                   
                             
                     void                               * binary_search(                               void                               * arg)                   
                     {                   
                             
                                         // Each thread checks 1/4 of the array for the key                   
                                         int                               thread_part = part++;                   
                                         int                               mid;                   
                             
                                         int                               low = thread_part * (MAX / 4);                   
                                         int                               high = (thread_part + 1) * (MAX / 4);                   
                             
                                         // search for the key until low < high                   
                                         // or key is found in any portion of array                   
                                         while                               (low < high && !found)  {                   
                             
                                         // normal iterative binary search algorithm                   
                                         mid = (high - low) / 2 + low;                   
                             
                                         if                               (a[mid] == key)  {                   
                                         found =                               true                               ;                   
                                         break                               ;                   
                                         }                   
                             
                                         else                               if                               (a[mid] > key)                   
                                         high = mid - 1;                   
                                         else                   
                                         low = mid + 1;                   
                                         }                   
                     }                   
                             
                             
                     // Driver Code                   
                     int                               main()                   
                     {                   
                                         pthread_t threads[MAX_THREAD];                   
                             
                                         for                               (                               int                               i = 0; i < MAX_THREAD; i++)                   
                                         pthread_create(&threads[i], NULL, binary_search, (                               void                               *)NULL);                   
                             
                                         for                               (                               int                               i = 0; i < MAX_THREAD; i++)                   
                                         pthread_join(threads[i], NULL);                   
                             
                                         // key found in array                   
                                         if                               (found)                   
                                         cout << key <<                               " found in array"                               << endl;                   
                             
                                         // key not found in array                   
                                         else                   
                                         cout << key <<                               " not found in array"                               << endl;                   
                             
                                         return                               0;                   
                     }                   

输出：

110 found in array

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章