查找算法
- 查找算法
- 查找的定義
- 數組和索引
- 二分查找
- 窮舉搜尋
- 并行搜尋
查找算法
查找的定義
查找:又稱檢索或查詢，是指在查找表中找出滿足一定條件的結點或記錄對應的操作。
查找表:在計算機中，是指被查找的資料對象是由同一個類型的記錄構成的集合，如順序表、連結清單、二叉樹和哈希表等。
查找效率:查找算法中的基本運算是通過記錄的關鍵字與給定值進行比較，是以查找的效率通常取決于比較所花的時間，而時間取決于比較的次數。通常以關鍵字與給定值進行比較的記錄個數的平均值來計算。
查找操作及分類
操作：
- 查找某個“特定的”資料元素是否成存在在查找表裡。
- 某個“特定的”資料元素的各種屬性。
- 在查找表中插入一個資料元素。
- 從查找表中删除某個資料元素。
分類:
若對查找表隻進行(1)或(2)兩種操作，則稱此類查找表為靜态查找表。
若在查找的過程中同時插入查找表中存在的資料元素，或者從查找表中删除已經存在的某個資料元素，則稱次類查找表為動态查找表。
數組和索引
索引把線性表分為若幹塊，每一塊中的元素存儲順序是任意的，但是塊與塊之間必須按關鍵字大小順序排列。即前一塊中的最大關鍵字值小于後一塊中的最小關鍵字值。
分塊以後，為了快速定義塊，還需要建立一個索引表，索引表中的一項對應于線性表中的塊，索引項由鍵域和鍊域組成。鍵域存放相應關鍵字的鍵值，鍊域存放指向本塊第一個節點和最後一個節點的指針，索引表按關鍵字由小到大的順序排列！
數組是特殊的塊索引（一個塊一個元素）：
[外鍊圖檔轉存失敗,源站可能有防盜鍊機制,建議将圖檔儲存下來直接上傳(img-xDbRyWBM-1635489015712)(查找算法.assets/image-20211028180054162.png)]
哈希表是非常經典的塊索引!
[外鍊圖檔轉存失敗,源站可能有防盜鍊機制,建議将圖檔儲存下來直接上傳(img-6LawbrgF-1635489015715)(查找算法.assets/image-20211028180620292.png)]
分塊查找的算法分兩步進行，首先确定所查找的節點屬于哪一塊，即在索引表中查找其所在的塊，然後在塊内查找待查詢的資料。由于索引表是遞增有序的，可采用二分查找，而塊内元素是無序的，隻能采用順序查找。（塊内元素較少，則不會對執行速度有太大的影響）
二分查找
二分查找法實質上是不斷地将有序資料集進行對半分割，并檢查每個分區的中間元素。再重 複根據中間數确定目标範圍并遞歸實行對半分割，直到中間數等于待查找的值或是目标數不在搜 索範圍之内！
代碼實作
#include<iostream>
using namespace std;
int BinarySearch(int* sorted, int len, int search)
{
int left = 0;
int right = 0;
int middle = 0;
left = 0;
right = len - 1;
while (left <= right)
{
middle = (left + right) / 2;
if (sorted[middle] == search)
{
return middle;
}
else if (sorted[middle] > search)
{
right = middle - 1;
}
else
{
left = middle + 1;
}
}
return -1;
}
int main(void)
{
int arr[] = { 1,3,5,16,58,74,169 };
int search = 3;
int index = BinarySearch(arr, sizeof(arr) / sizeof(arr[0]),search);
cout << index;
return 0;
} 如果要實作其他類型的比較查找
注意用void*類型接收不同類型，根據傳進來類型的不同調用對應的比較函數。
代碼實作
#include<iostream>
using namespace std;
int int_compare(const void* key1, const void* key2)
{
const int* ch1 = (const int*)key1;
const int* ch2 = (const int*)key2;
return *ch1 - *ch2;
}
int char_compare(const void* key1, const void* key2)
{
const char* ch1 = (const char*)key1;
const char* ch2 = (const char*)key2;
return *ch1 - *ch2;
}
int BinarySearch(void* sorted, int len,int elemSize,void *search, int(*compare)(const void* key1, const void* key2))
{
int left = 0;
int right = 0;
int middle = 0;
left = 0;
right = len - 1;
while (left <= right)
{
int ret = 0;
middle = (left + right) / 2;
ret = compare( (char*)sorted+(middle * elemSize),search);
if (ret == 0)
{
return middle;
}
else if (ret > 0)
{
right = middle - 1;
}
else
{
left = middle + 1;
}
}
return -1;
}
int main(void)
{
int arr[] = { 1,3,5,16,58,74,169 };
int search = 3;
int index = BinarySearch(arr, sizeof(arr) / sizeof(arr[0]),sizeof(int),&search,int_compare);
cout << index;
return 0;
} 補充:上面代碼中為什麼要轉成char類型指針
ret = compare( (char*)sorted+(middle * elemSize),search); 什麼類型的指針，增加偏移量的大小的是不同的。
例如：
char*指針 +1，記憶體偏移1位元組
int* 指針 +1，記憶體偏移4位元組 因為我們的運算加的是對應數組元素類型的大小*middle,求出偏移的位元組個數，是以轉成char類型指針，可以保證我們加了幾個這個類型的大小等同于與數組第一個元素相距了幾個元素，得到對應的位址。
指針的運算！！！
如下圖所示，+1和+4，指向的是同一個位址。
[外鍊圖檔轉存失敗,源站可能有防盜鍊機制,建議将圖檔儲存下來直接上傳(img-fLQp4abR-1635489015717)(查找算法.assets/image-20211028203724495.png)]
窮舉搜尋
有 20 枚硬币，可能包括 4 種類型：1 元、5 角、1 角和 5 分。
已知 20 枚硬币的總價值為 10 元，求各種硬币的數量。
例如：4、11、5、0 就是一種方案。而 8、2、10、 0 是另一個可能的方案，顯然方案并不是
唯一的，請編寫程式求出類似這樣的不同的方案一共有多少種？
（1）程式設計思路。
直接對四種類型的硬币的個數進行窮舉。其中，1 元最多 10 枚、5 角最多 20 枚、1 角最多 20 枚、5 分最多 20 枚。
如果以元為機關，則 5 角、1 角、5 分會化成浮點型資料，容易計算出錯。可以将 1 元、5 角、1 角、5 分變成 100 分、50 分、10 分和 5 分，進而全部采用整型資料處理。
代碼實作:
#include<iostream>
using namespace std;
int main(void)
{
int a100 = 0;//一進制硬币的數量
int a50 = 0;
int a10 = 0;
int a5 = 0;
int count = 0;//可行方案總數
//for循環可以進行優化，根據上一個紙币面額所花費錢的多少
for (a100 = 0; a100 <= 10; a100++)
{
for (a50 = 0; a50 <= 20; a50++)
{
for (a10 = 0; a10 <= 20; a10++)
{
for (a5 = 0; a5 <= 20; a5++)
{
if (a100 * 100 + a50 * 50 + a10 * 10 + a5 * 5 == 1000 && (a100 + a50 + a10 + a5 == 20))
{
cout << "a100:" << a100 << " " << "a50:" << a50 << " " << "a10:" << a10 << " " << "a5:" << a5 << endl;
count++;
}
}
}
}
}
cout << "一共有" << count << "種可行方案" << endl;
return 0;
} 窮舉法(枚舉法)的基本思想是:列出所有的可能情況，逐個判斷有哪些是符合問題所要求 的條件，進而得到問題的全部解答。
它利用計算機運算速度快、精确度高的特點，對要解決問題的所有可能情況，一個不漏地進行檢查，從中找出符合要求的答案。
用窮舉法解決問題,通常可以從兩個方面進行分析:
（1）問題所涉及的情況：問題所涉及的情況有哪些，情況的種數必須可以确定。把它描述出來。應用窮舉時對問題所涉及的有限種情形必須一一列舉，既不能重複，也不能遺漏。重複列 舉直接引發增解，影響解的準确性；而列舉的遺漏可能導緻問題解的遺漏。
（2）答案需要滿足的條件：分析出來的這些情況，需要滿足什麼條件，才成為問題的答案。把這些條件描述出來。
并行搜尋
并發的基本概念：
所謂并發就是在同一實體上的多個事件同時發生。并發程式設計是指在同一台計算機上"同時"處理多個任務。
程序：
通常每個程序對應一個在運作中的執行程式，比如，QQ 和微信運作的時候，他們分别是不同的程序。
任一時刻，單個 CPU 一次隻能運作一個程序，此時其他程序處于非運作狀态。
線程：
一個程序可以擁有多個線程，每個線程可以可以獨立并行執行，多個線程共享同一程序的資源，受程序管理。
#include<iostream>
#include<time.h>
#include<stdio.h>
#include<windows.h>
using namespace std;
#define TEST_SIZE (1024*1024*200)
#define NUMBER 20
typedef struct _search
{
int* data;//搜尋的資料集
size_t start;//搜尋的開始位置
size_t end;//搜尋的結束位置
size_t count;//搜尋結果
}search;
DWORD WINAPI ThreadProc(void* lpParm)
{
search* s = (search*)lpParm;
time_t start, end;
cout << "新的線程開始執行..." << endl;
time(&start);
for (int j = 0;j <10;j++)
{
for (size_t i = s->start; i <= s->end; i++)
{
if (s->data[i] == NUMBER)
{
s->count++;
}
}
}
time(&end);
cout << "程序所用時間:" << end - start << endl;
return 0;
}
int main(void)
{
int* data = NULL;
int count = 0;
int mid = 0;
search s1, s2;
data = new int[TEST_SIZE];
for (int i = 0; i <TEST_SIZE; i++)
{
data[i] = i;
}
mid = TEST_SIZE / 2;
s1.data = data;
s1.start = 0;
s1.end = mid;
s1.count = 0;
s2.data = data;
s2.start = mid + 1;
s2.end = TEST_SIZE - 1;
s2.count = 0;
DWORD threadID1;//線程1的身份證
HANDLE hthread1;//線程1的句柄
DWORD threadID2;//線程2的身份證
HANDLE hthread2;//線程2的句柄
//建立線程
hthread1 = CreateThread(NULL, 0, ThreadProc, &s1, 0, &threadID1);
hthread2 = CreateThread(NULL, 0, ThreadProc, &s2, 0, &threadID2);
WaitForSingleObject(hthread1, INFINITE);
WaitForSingleObject(hthread2, INFINITE);
cout << s1.count + s2.count << endl;
return 0;
} ![【資料結構】 醫院選址[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)