快速搜尋法

Question

有很多人都在討論有關【快速排序法】，但好像都沒有人提到【快速搜尋法】，雖然【二分搜尋法】是在搜尋法中最快速的搜尋方式，但因為資料還是必須要先行排序之後，才能進行搜尋的功能。試想，有什麼方式，可以不需用到排序的功能，亦能做到高效率的搜尋功能？題外話：個人寫的快速排序法，有興趣的人可以幫忙取個名稱吧！

我個人是有想到一個方法(不知大家是否認同)，就是直接將預搜尋的陣列資料用 Join 將資料整合成為一個字串，然後再利用 InStr 搜尋字串中的資料，這樣應該也算是快速搜尋吧！
因為實在想不出解答要選給誰，就交付投票吧！
若無法發表意見，就直接利用知識 的功能寄信給我吧！

Answer 1

根據我所了解的搜尋法,提共給你:
搜尋法有以下三類：
第一類：順序搜尋法、二分搜尋法、比例搜尋法、自然搜尋法、等等。
第二類：除了第一類搜尋法以外還有、亂數搜尋法、基因演算法、等等。
第三類：樹狀搜尋法、智慧搜尋法、等等。
第二類雖然像第一類搜尋資料，比對資料，而第一類必須找到完全相同的資料才算找到，而第二類則找到接近的資料就算完成，但第三類與一、二類大不相同，它是要找到各種資料、步驟、方法等等之排列組合，符合要求才算完成。
　　“基因演算法＂雖然叫“演算法＂，但其實它也是搜尋法。
　　除了“順序搜尋法＂、“二分搜尋法＂、“基因演算法＂、“樹狀搜尋法＂以外，其他都是我自己取的名稱，所以可能不是學術界的專有名詞。
　　這三類的速度都是，後者比前者快。
　　“順序搜尋法＂在第一類及第二類都是最慢的。
　　你的問題屬於第一類，以下對第一類進一步的說明：
　　“順序搜尋法＂雖然最慢，但是資料如果沒有排序，也只好使用它。假如資料有排序則可用“二分搜尋法＂、“比例搜尋法＂、“自然搜尋法＂、……等等。
　　“二分搜尋法＂是不分青紅皂白，從中間就切下去，然後看看要找的資料在前半段還是後半段，然後再從那一段不分青紅皂白，再從中間又切下去，直到找到為止。切下去的位置計算如下：前端的位置為Ｌ；後端的位置為Ｒ，切下去的位置約為（Ｌ＋Ｒ）／２（因為算出來的值有可能為小數，所以我寫“約為＂）。
“比例搜尋法＂（我在網路上找到“插補搜尋法＂，就是“比例搜尋法＂）是按照比例切割，切下去的位置計算如下：前端的位置為Ｌ，資料為ＶＬ；後端的位置為Ｒ，資料為ＶＲ，要找的比對資料為ＶＸ，切下去的位置約為（（ＶＸ－ＶＬ）＊（Ｌ＋Ｒ）／（ＶＲ－ＶＬ））＋ＶＬ，然後看看要找的資料在前段還是後段，然後再設Ｌ、ＶＬ、Ｒ、ＶＲ，然後再繼續切，這樣的搜尋一搬來講，比“二分搜尋法＂快很多。但有些資料雖然排序了，但遞增的情況很不均勻，一開始，ＶＸ就非常接近ＶＬ或ＶＲ，所以有時這種搜尋速度會低於“二分搜尋法＂，甚至低於“順序搜尋法＂。
為了彌補“比例搜尋法＂的缺點，採用“自然搜尋法＂，切下去的位置約為（（ＶＸ－ＶＬ）＊（Ｌ＋Ｒ）／（ＶＲ－ＶＬ））＋ＶＬ＋ｄ，ｄ為一個小整數，當ＶＸ較接近ＶＬ時，ｄ為正值，當ＶＸ較接近ＶＲ時，ｄ為負值，這是為了避免當ＶＸ非常接近ＶＬ或ＶＲ時，切下去後ＶＸ落在較大塊那一段，加了ｄ值，ＶＸ比較會落在較小塊那一段，因此平均速度會比“二分搜尋法＂、“比例搜尋法＂還快。
當有一大疊資料，約1000張，由小到大，由左到右順序排列，編號大約由1到1000，但裏面有些空洞，有些重複，而編號第950張，大約靠右1/20的地方，就因為裏面的資料不是平均遞增，所以你要找的話，你可能會在大約靠右1/20~1/10的地方抽出1張，而不是從中間抽，這是人類很自然行成的搜尋方式，所以我成他為“自然搜尋法＂。
第二類的“比例搜尋法＂約1986我寫“幾何運算＂程式時，有寫過，但程式遺失，不過以你的能力，寫“比例搜尋法＂及“自然搜尋法＂因該沒問題，或許還有比這兩種還好的方法，例如將“二分搜尋法＂與“自然搜尋法＂混合，或切下去的位置有更智慧的計算，我們稱它為什麼“搜尋法＂好呢？暫時取名為“智慧搜尋法＂好嗎？所以說以上的“搜尋法＂名稱只是臨時取的，重要的是那種“搜尋法＂的內容及方法。
至於你寫的“排序法＂，我暫時稱它為“Liu-Liu排序法＂，不管它的名稱為何，它是你的智慧財產，但要符合兩個條件：
１．往前追朔，古今中外，沒有人的“排序法＂和你雷同。（不需要往後追朔）
２．這個“排序法＂確實是你的著作。（不一定要申請專利）
這樣它就是你的智慧財產，法律上是承認的，因為它的所有權屬於你，所以你有權出售它，也有權利將它貢獻給大家。

2006-12-09 10:04:34 補充：
Liu-Liu 你好
我寫的象棋程式,是屬於第三類搜尋法,且是樹狀搜尋法與智慧搜尋法、合並使用,但棋力不強(1GMz CPU,約 1 段).
知識＋改板後,發問中及投票的問題,我無法看到發表意見內容,也無法發表意見,不知知識等級為專家的你,是否可以看到及使用,請你回應時使用補充內容的方式,謝謝!
悠悠深藍 你好
謝謝你提供的答案,我有一些想和你交流的地方,但發表意見功能我無法使用.

Answer 2

台灣首家合法娛樂城開幕囉!

體育博彩、真人對戰、現場遊戲、彩球

投注高賠率，歡迎您來體驗!

官方網站 aa777.net

Answer 3

首先，可以用雜湊函數解決您的提問．
假設有N筆資料，這N筆資料安排在陣列中，不用排序，每個關鍵值經過雜湊函式，恰好對上每一個紀錄，因此只要透過雜湊函式就可以直接計算鍵值，一步就找到紀錄．
例如：A為00001 , B為00010，而關鍵字為AB，雜湊為0000100010，所以一步就可以找到紀錄了．這是簡單的範例．
當然這麼完美的雜湊函式，實在難以想像，在數學上是個極端的例子，正常情況下會發生"碰撞"，至少有三種解決方式．
分離串練：當衝突發生時，便將索引值相同的紀錄用練狀結構串聯起來．形成N條練．當索引值找到該位置時，可以用循序搜尋一一對印，這樣至少第一步的出發點就可以找到紀錄所在範圍，然後循序搜尋．以分離串練搜尋時，比較動作次數不管是搜尋成功或失敗，都是循序法的1/N．
線性探索：類似分離串練，只不過是建立較大的空間，擺放紀錄．當索引值對應到N時，就開始比對，若不對則比較N+1筆，這樣就可以達到目的．
雙重雜湊：當發生碰撞時，在建立一個雜湊索引值，就變成雙重雜湊，如此就可以解決問題，探索的次數比線性探索還要少．資料不多時，兩步就可以搜尋的到了．
所以您提到的問題，其實很早以前數學家就已經在研究了．
題外話：您所寫的快速排序法，如果有數學驗證，可以發表期刊．

Answer 4

如果是找尋陣列中符合的值
除了線性搜尋與二元搜尋外，應該是沒有其他方法了。

Answer 5

Liu-Liu
能夠先起個頭嗎?譬如說在某文章搜尋某字什麼的.

Answer 6

快速搜尋...?
這我倒是從來都沒想過...(~"~

Liu-Liu大~
你寫的快速排序法的這一段，讓我想到有一個叫做謝爾的排序法...
For i = 0 To Val(IIf(UBound(num) Mod 2 = 0, Int(UBound(num) / 2) - 1, Int(UBound(num) / 2)))
　　...
Next i