⑴ 什麼是查找法
演算法思想：
將數列按有序化(遞增或遞減)排列，查找過程中採用跳躍式方式查找，即先以有序數列的中點位置為比較對象，如果要找的元素值小於該中點元素，則將待查序列縮小為左半部分，否則為右半部分。通過一次比較，將查找區間縮小一半。
折半查找是一種高效的查找方法。它可以明顯減少比較次數，提高查找效率。但是，折半查找的先決條件是查找表中的數據元素必須有序。
演算法步驟描述：
step1 首先確定整個查找區間的中間位置
mid = （ left + right ）/ 2
step2 用待查關鍵字值與中間位置的關鍵字值進行比較；
若相等，則查找成功
若大於，則在後（右）半個區域繼續進行折半查找
若小於，則在前（左）半個區域繼續進行折半查找
Step3 對確定的縮小區域再按折半公式，重復上述步驟。最後，得到結果：要麼查找成功， 要麼查找失敗。
折半查找的存儲結構採用一維數組存放。
折半查找演算法舉例
對給定數列（有序）{ 3，5，11，17，21，23，28，30，32，50}，按折半查找演算法，查找關鍵字值為30的數據元素。
折半查找的演算法討論：
優點: ASL≤log2n，即每經過一次比較,查找范圍就縮小一半。經log2n 次計較就可以完成查找過程。
缺點：因要求有序，所以要求查找數列必須有序，而對所有數據元素按大小排序是非常費時的操作。另外，順序存儲結構的插入、刪除操作不便利。
考慮：能否通過一次比較拋棄更多的部分（即經過一次比較，使查找范圍縮得更小），以達到提高效率的目的。……？
可以考慮把兩種方法（順序查找和折半查找）結合起來，即取順序查找簡單和折半查找高效之所長，來達到提高效率的目的？實際上這就是分塊查找的演算法思想。
例如：[問題分析] 由於數據按升序排列,故用折半查找最快捷.
program binsearch;
const max=10;
var num:array[1..max] of integer;
i,n:integer;
procere search(x,a,b:integer);
var mid:integer;
begin
if a=b then
if x=num[a] then writeln('Found:',a) else writeln('Number not found')
else begin
mid:=(a+b) div 2;
if x>num[mid] then search(x,mid,b);
if x<num[mid] then search(x,a,mid);
if x=num[mid] then writeln('Found:',mid);
end;
end;
begin
write('Please input 10 numbers in order:');
for i:=1 to max do read(num);
write('Please input the number to search:');
readln(n);
search(n,1,max);
end.
Java風格的代碼舉例：
//使用折半法進行查找
int getIndex(int[] nList, int nCount, int nCode) {
int nIndex = -1;
int jMin = 0;
int jMax = nCount - 1;
int jCur = (jMin+jMax)/2;
do
{
if(nList[jCur] > nCode) {
jMax--;
} else if(nList[jCur] < nCode) {
jMin++;
} else if(nList[jCur] == nCode) {
nIndex = jCur;
break;
}
jCur = (jMin + jMax)/2;
} while(jMin < jMax);
return nIndex;
}
二分查找的性能說明
雖然二分查找的效率高，但是要將表按關鍵字排序。而排序本身是一種很費時的運算。既使採用高效率的排序方法也要花費 O(n lg n) 的時間。
二分查找只適用順序存儲結構。為保持表的有序性，在順序結構里插入和刪除都必須移動大量的結點。因此，二分查找特別適用於那種一經建立就很少改動、而又經常需要查找的線性表。
對那些查找少而又經常需要改動的線性表，可採用鏈表作存儲結構，進行順序查找。鏈表上無法實現二分查找
二分查找的C#實現代碼：
using System;
using System.Collections.Generic;
using System.Text;
namespace BinschDemo
{
public class BinschDemo
{
public static int Binsch(int[] a, int key)
{
int low = 1;
int high = a.Length;
while (low <= high)
{
int mid = (low + high) / 2;
if (key == a[mid])
{
return mid; //返回找到的索引值
}
else
{
if (key < a[mid])
high = mid - 1;
else
low = mid + 1;
}
}
return -1; //查找失敗
}
static void Main(string[] args)
{
Console.WriteLine("請輸入10個遞增數字: ");
int[] list = new int[10];
for (int i = 0; i < 10; i++)
{
Console.Write("數字 : ", i);
list = Convert.ToInt32(Console.ReadLine());
}
Console.Write("請輸入一個你要查找的數字:");
int find = Convert.ToInt32(Console.ReadLine());
int result = Binsch(list, find);
Console.WriteLine(result);
}
}
}
分塊查找又索引查找，它主要用於「分塊有序」表的查找。所謂「分塊有序」是指將線性表L（一維數組）分成m個子表（要求每個子表的長度相等），且第i+1個子表中的每一個項目均大於第i個子表中的所有項目。「分塊有序」表應該包括線性表L本身和分塊的索引表A。因此，分塊查找的關鍵在於建立索引表A。
（1）建立索引表A（二維數組）
索引表包括兩部分：關鍵字項（子表中的最大值）和指針項（子表的第一項在線性表L中位置）
索引表按關鍵字有序的。
例如：線性表L（有序）為：1 2 3 4 5 6 7 8 9 10 11 12
分成m=3個子表：{1 2 3 4} {5 6 7 8} {9 10 11 12}
索引表A：二維數組：第一列為每個子表的最大值 ，第二列為每個子表的起始地址
即： 4 0
8 4
12 8
（2）利用索引表A，確定待查項X所在的子表（塊）。
（3）在所確定的子表中可以用「折半查找」法搜索待查項X；若找到則輸出X；否則輸出未找到信息。
⑵ 二分查找演算法實現（圖解）與實例
當我們要從一個序列中查找一個元素的時候，二分查找是一種非常快速的查找演算法，二分查找又叫折半查找。
它對要查找的序列有兩個要求，一是該序列必須是有序的（即該序列中的所有元素都是按照大小關系排好序的，升序和降序都可以，本文假設是升序排列的），二是該序列必須是順序存儲的。
如果一個序列是無序的或者是鏈表，那麼該序列就不能進行二分查找。之所以被查找的序列要滿足這樣的條件，是由二分查找演算法的原理決定的。
二分查找又稱折半查找，優點是比較次數少，查找速度快，平均性能好；其缺點是要求待查表為有序表，且插入刪除困難。因此，折半查找方法適用於不經常變動而查找頻繁的有序列表。
二分查找能應用於任何類型的數據，只要能將這些數據按照某種規則進行排序。然而，正因為它依賴於一個有序的集合，這使得它在處理那些頻繁插入和刪除操作的數據集時不太高效。這是因為，對於插入和操作來說，為了保證查找過程正常進行，必須保證數據集始終有序。相對於查找來說，維護一個有序數據集的代價更高。此外，元素必須存儲在連續的空間中。因此，當待搜索的集合是相對靜態的數據集時，此時使用二分查找是最好的選擇。
二分查找演算法的原理如下：
二分查找之所以快速，是因為它在匹配不成功的時候，每次都能排除剩餘元素中一半的元素。因此可能包含目標元素的有效范圍就收縮得很快，而不像順序查找那樣，每次僅能排除一個元素。
二分查找法實質上是不斷地將有序數據集進行對半分割，並檢查每個分區的中間元素。
此實現過程的實施是通過變數left和right控制一個循環來查找元素（其中left和right是正在查找的數據集的兩個邊界值）。
二分查找的時間復雜度取決於查找過程中分區數可能的最大值。對於一個有n個元素的數據集來說，最多可以進行O(㏒₂n)次分區。對於二分查找，這表示最終可能在最壞的情況下執行的檢查的次數：例如，在沒有找到目標時。所以二分查找的時間復雜度為O(㏒₂n)。
參考：
https://www.html.cn/qa/other/23018.html
https://www.cnblogs.com/idreamo/p/9000762.html
⑶ 常用查找演算法
查找演算法可分為兩種： 無序查找 和 有序查找 ，顧名思義，無序查找就是查找數列中的數是無序的，有序查找要求所查找數列是已經按照一定的規律排好序了，常見演算法中大多都是無序查找。下面一一介紹幾種常見的查找演算法。
顧名思義，就是將所查找數列構建成一顆樹，其中最常見的是構建成一顆 二叉查找樹（左子節點的值均小於父節點的值，右子節點的值均大於父節點的值） ，然後通過遍歷比較得出查找結果。
⑷ 基本演算法——二分查找演算法
二分查找也稱折半查找（Binary Search），它是一種效率較高的查找方法。但是，折半查找要求線性表必須採用順序存儲結構，而且表中元素按關鍵字有序排列。
1.條件
（1）必須採用 順序存儲結構 。
（2）必須按關鍵字大小有序排列。
2.步奏
（1）首先，假設表中元素是按升序排列，將表中間位置記錄的 關鍵字 與查找關鍵字比較，如果兩者相等，則查找成功；
（2）否則利用中間位置 記錄 將表分成前、後兩個子表，如果中間位置記錄的關鍵字大於查找關鍵字，則進一步查找前一子表，否則進一步查找後一子表；
（3）重復以上過程，直到找到滿足條件的 記錄 ，使查找成功，或直到子表不存在為止，此時查找不成功。
3.舉例
有一組元素{1，2，3，4，5，6，7，8，9}，如何查到元素為3。
（1）找到數組中中間元素值5，不等於3，所以把數組分為{1，2，3，4}，{5，6，7，8，9}；
（2）因為5大於3，所以3在前一個數組{1，2，3，4}中查找，中間變數2，3比2大，所以在{3，4}中查詢；
（3）查詢到3=3，成功。
4.復雜度
最好的情況下，1次查詢成功；最壞的情況下，查詢到最後兩個數或者最後也查不到相等數，時間復雜度為O(log2n)。
⑸ C語言編寫數據結構查找演算法
實驗五 查找的實現
一、 實驗目的
1．通過實驗掌握查找的基本概念；
2．掌握順序查找演算法與實現；
3．掌握折半查找演算法與實現。
二、 實驗要求
1． 認真閱讀和掌握本實驗的參考程序。
2． 保存程序的運行結果，並結合程序進行分析。
三、 實驗內容
1、建立一個線性表，對表中數據元素存放的先後次序沒有任何要求。輸入待查數據元素的關鍵字進行查找。為了簡化演算法，數據元素只含一個整型關鍵字欄位，數據元素的其餘數據部分忽略不考慮。建議採用前哨的作用，以提高查找效率。
2、查找表的存儲結構為有序表，輸入待查數據元素的關鍵字利用折半查找方法進行查找。此程序中要求對整型量關鍵字數據的輸入按從小到大排序輸入。
一、順序查找
順序查找代碼：
#include"stdio.h"
#include"stdlib.h"
typedef struct node{
intkey;
}keynode;
typedef struct Node{
keynoder[50];
intlength;
}list,*sqlist;
int Createsqlist(sqlist s)
{
inti;
printf("請輸入您要輸入的數據的個數:\n");
scanf("%d",&(s->length));
printf("請輸入您想輸入的%d個數據;\n\n",s->length);
for(i=0;i<s->length;i++)
scanf("%d",&(s->r[i].key));
printf("\n");
printf("您所輸入的數據為:\n\n");
for(i=0;i<s->length;i++)
printf("%-5d",s->r[i].key);
printf("\n\n");
return1;
}
int searchsqlist(sqlist s,int k)
{
inti=0;
s->r[s->length].key=k;
while(s->r[i].key!=k)
{
i++;
}
if(i==s->length)
{
printf("該表中沒有您要查找的數據！\n");
return-1;
}
else
returni+1;
}
sqlist Initlist(void)
{
sqlistp;
p=(sqlist)malloc(sizeof(list));
if(p)
returnp;
else
returnNULL;
}
main()
{
intkeyplace,keynum;//
sqlistT;//
T=Initlist();
Createsqlist(T);
printf("請輸入您想要查找的數據的關鍵字:\n\n");
scanf("%d",&keynum);
printf("\n");
keyplace=searchsqlist(T,keynum);
printf("您要查找的數據的位置為:\n\n%d\n\n",keyplace);
return2;
}
順序查找的運行結果：
二、折半查找
折半查找代碼：
#include"stdio.h"
#include"stdlib.h"
typedef struct node{
intkey;
}keynode;
typedef struct Node{
keynoder[50];
intlength;
}list,*sqlist;
int Createsqlist(sqlist s)
{
inti;
printf("請輸入您要輸入的數據的個數:\n");
scanf("%d",&(s->length));
printf("請由大到小輸入%d個您想輸入的個數據;\n\n",s->length);
for(i=0;i<s->length;i++)
scanf("%d",&(s->r[i].key));
printf("\n");
printf("您所輸入的數據為:\n\n");
for(i=0;i<s->length;i++)
printf("%-5d",s->r[i].key);
printf("\n\n");
return1;
}
int searchsqlist(sqlist s,int k)
{
intlow,mid,high;
low=0;
high=s->length-1;
while(low<=high)
{
mid=(low+high)/2;
if(s->r[mid].key==k)
returnmid+1;
elseif(s->r[mid].key>k)
high=mid-1;
else
low=mid+1;
}
printf("該表中沒有您要查找的數據!\n");
return-1;
}
sqlist Initlist(void)
{
sqlistp;
p=(sqlist)malloc(sizeof(list));
if(p)
returnp;
else
returnNULL;
}
main()
{
intkeyplace,keynum;//
sqlistT;//
T=Initlist();
Createsqlist(T);
printf("請輸入您想要查找的數據的關鍵字:\n\n");
scanf("%d",&keynum);
printf("\n");
keyplace=searchsqlist(T,keynum);
printf("您要查找的數據的位置為:\n\n%d\n\n",keyplace);
return2;
}
折半查找運行結果：
三、實驗總結：
該實驗使用了兩種查找數據的方法（順序查找和折半查找），這兩種方法的不同之處在於查找方式和過程不同，線性表的創建完全相同，程序較短，結果也一目瞭然。
⑹ 最好的查找演算法是什麼
沒有最好只有更好
對不同特徵的數據也有不同的查找演算法，所有的查找演算法都是針對某一特徵的數據進行優化的，比如用散列表查找很快的數據用二分發就不一定快，散列表用不同的哈希演算法查找性能也大不相同。
⑺ 數學建模演算法總結
無總結反省則無進步
寫這篇文章，一是為了總結之前為了准備美賽而學的演算法，而是將演算法羅列並有幾句話解釋方便以後自己需要時來查找。
數學建模問題總共分為四類：
1. 分類問題 2. 優化問題 3. 評價問題 4. 預測問題
我所寫的都是基於數學建模演算法與應用這本書
一 優化問題
線性規劃與非線性規劃方法是最基本經典的：目標函數與約束函數的思想
現代優化演算法：禁忌搜索；模擬退火；遺傳演算法；人工神經網路
模擬退火演算法：
簡介：材料統計力學的研究成果。統計力學表明材料中不同結構對應於粒子的不同能量水平。在高溫條件下，粒子的能量較高，可以自由運動和重新排列。在低溫條件下，粒子能量較低。如果從高溫開始，非常緩慢地降溫（此過程稱為退火），粒子就可以在每個溫度下達到熱平衡。當系統完全被冷卻時，最終形成處於低能狀態的晶體。
思想可用於數學問題的解決 在尋找解的過程中，每一次以一種方法變換新解，再用退火過程的思想，以概率接受該狀態（新解） 退火過程：概率轉化，概率為自然底數的能量/KT次方
遺傳演算法： 遺傳演算法是一種基於自然選擇原理和自然遺傳機制的搜索演算法。模擬自然界中的生命進化機制，在人工系統中實現特定目標的優化。
遺傳演算法的實質是通過群體搜索技術（？），根據適者生存的原則逐代進化，最終得到最優解或准最優解。
具體實現過程（P329~331）
* 編碼
* 確定適應度函數（即目標函數）
* 確定進化參數：群體規模M，交叉概率Pc，變異概率Pm，進化終止條件
* 編碼
* 確定初始種群，使用經典的改良圈演算法
* 目標函數
* 交叉操作
* 變異操作
* 選擇
改良的遺傳演算法
兩點改進 ：交叉操作變為了以「門當戶對」原則配對，以混亂序列確定較差點位置 變異操作從交叉操作中分離出來
二 分類問題（以及一些多元分析方法）
* 支持向量機SVM
* 聚類分析
* 主成分分析
* 判別分析
* 典型相關分析
支持向量機SVM： 主要思想：找到一個超平面，使得它能夠盡可能多地將兩類數據點正確分開，同時使分開的兩類數據點距離分類面最遠
聚類分析（極其經典的一種演算法）： 對樣本進行分類稱為Q型聚類分析 對指標進行分類稱為R型聚類分析
基礎：樣品相似度的度量——數量化，距離——如閔氏距離
主成分分析法： 其主要目的是希望用較少的變數去解釋原來資料中的大部分變異，將掌握的許多相關性很高的變數轉化成彼此相互獨立或不相關的變數。通常是選出比原始變數個數少，能解釋大部分資料中的變異的幾個新變數，及主成分。實質是一種降維方法
判別分析： 是根據所研究的個體的觀測指標來推斷個體所屬類型的一種統計方法。判別准則在某種意義下是最優的，如錯判概率最小或錯判損失最小。這一方法像是分類方法統稱。 如距離判別，貝葉斯判別和FISHER判別
典型相關分析： 研究兩組變數的相關關系 相對於計算全部相關系數，採用類似主成分的思想，分別找出兩組變數的各自的某個線性組合，討論線性組合之間的相關關系
三 評價與決策問題
評價方法分為兩大類，區別在於確定權重上：一類是主觀賦權：綜合資訊評價定權；另一類為客觀賦權：根據各指標相關關系或各指標值變異程度來確定權數
* 理想解法
* 模糊綜合評判法
* 數據包絡分析法
* 灰色關聯分析法
* 主成分分析法（略）
* 秩和比綜合評價法 理想解法
思想：與最優解（理想解）的距離作為評價樣本的標准
模糊綜合評判法 用於人事考核這類模糊性問題上。有多層次模糊綜合評判法。
數據包絡分析法 是評價具有多指標輸入和多指標輸出系統的較為有效的方法。是以相對效率為概念基礎的。
灰色關聯分析法 思想：計算所有待評價對象與理想對象的灰色加權關聯度，與TOPSIS方法類似
主成分分析法（略）
秩和比綜合評價法 樣本秩的概念： 效益型指標從小到大排序的排名 成本型指標從大到小排序的排名 再計算秩和比，最後統計回歸
四 預測問題
* 微分方程模型
* 灰色預測模型
* 馬爾科夫預測
* 時間序列（略）
* 插值與擬合（略）
* 神經網路
微分方程模型 Lanchester戰爭預測模型。。
灰色預測模型 主要特點：使用的不是原始數據序列，而是生成的數據序列 優點：不需要很多數據·，能利用微分方程來充分挖掘系統的本質，精度高。能將無規律的原始數據進行生成得到規律性較強的生成序列。 缺點：只適用於中短期預測，只適合指數增長的預測
馬爾科夫預測 某一系統未來時刻情況只與現在狀態有關，與過去無關。
馬爾科夫鏈
時齊性的馬爾科夫鏈
時間序列（略）
插值與擬合（略）
神經網路（略）
⑻ 標題討論1.如何評價一個查找演算法
評價一個查找演算法是用平均查找長度來進行評價。使用平均查找長度，即關鍵字的平均比較次數來評價查找演算法，這個值越大，對應的查找演算法的效率越低。
⑼ 查找--有序表查找(折半查找，插值查找，斐波拉契查找)
引言
如果待查找的數組是有序的，那麼此時的查找就是有序表查找，這對於查找的幫助是很大的。屬於有序表查找的有：折半查找（二分查找）、插值查找以及斐波那契查找。
1. 折半查找
折半查找又稱為二分查找，是一種效率較高的查找演算法。折半查找的先決條件是查找表中的數據元素排列必須是有序的。折半查找先以有序數列的中點位置為比較對象，如果要找的元素值小於中點位置元素，則將待查序列縮小為左半部分，否則為右半部分。通過一次比較，可以將查找的區間縮小一半，每次比較，都可以將當前查找范圍縮小至一般，可以明顯的減少比較的次數，提高查找效率。
時間復雜度：O(logn)
演算法實現：
2. 插值查找
插值查找是二分查找演化而來，相比於二分查找(折半),該演算法考慮的是每次折的時候折多少,即不一定是1/2;如在一本字典中找"abstract"這個單詞,我們自己來操作肯定是先翻到字典開始的那一小部分,而不是從字典的中間開始進行折半查找。
在二分查找中mid=(low+high)/2=low+1/2*(high-low),插值查找就是對1/2(系數,或者說比例)進行改變，它將1/2變成 (key - array[low])/(array[high] - array[low]),其實就是計算線性比例。
時間復雜度：O(logn)
因為插值查找是依賴線性比例的，如果當前數組分布不是均勻的，那麼該演算法就不合適。
演算法實現：
3. 斐波那契查找
根據前面二分查找以及插值查找來看，有序表上的查找的關鍵就是如何分割當前查找的區域（二分查找對半分割，差值查找按線性比例分割），說到分割，還有一個著名的分割方式就是黃金分割。
斐波那契數列，又稱黃金分割數列，指的是這樣一個數列：1、1、2、3、5、8、13、21、····，在數學上，斐波那契被遞歸方法如下定義：F(1)=1，F(2)=1，F(n)=f(n-1)+F(n-2) （n>=2）。該數列越往後相鄰的兩個數的比值越趨向於黃金比例值（0.618）
所以我們可以根據斐波那契數列對當前區域進行分割 :)
查找演算法：在斐波那契數列找一個等於略大於查找表中元素個數的數F(n)，將原查找表擴展為長度為F(n)(如果要補充元素，則補充重復最後一個元素，直到滿足數組元素個數為F(n)個元素)，完成後進行斐波那契分割，即F(n)個元素分割為前半部分F(n-1)個元素，後半部分F(n-2)個元素，找出要查找的元素在那一部分並遞歸，直到找到。
時間復雜度：O(logn)，平均性能優於二分查找。
演算法實現：
結束語
以上三種查找演算法中，都依賴於順序表，三者的區別本質上就是分割點選的不同。在分割點的選擇中，折半查找 mid=(low+high)/2是加法與除法運算；插值查找mid = low+(key-array[low])/(array[high]-array[low])*(high-low)是復雜的四則運算；斐波那契查找mid=low+fib[k-1]-1是簡單的加減運算。在海量數據查找過程中細微的差別會影響最終的效率。
三種查找演算法，各有優劣，實際開發可以根據數據的特點綜合考慮再做出選擇。