首頁 常見問題 適用於折半查找的表格的儲存方式及元素排列要求為什麼?

適用於折半查找的表格的儲存方式及元素排列要求為什麼?

Aug 31, 2020 pm 03:27 PM

適用於折半查找的表的儲存方式及元素排列要求為:順序方式存儲,元素有序。二分查找是一種效率較高的查找方法,要求線性表必須採用順序儲存結構,且表格中元素依關鍵字有序排列。

適用於折半查找的表格的儲存方式及元素排列要求為什麼?

二分查找也稱為折半查找(Binary Search),它是一種效率較高的查找方法。但是,折半查找要求線性表必須採用順序儲存結構,且表格中元素依關鍵字有序排列。

首先,假設表中元素是按升序排列,將表中間位置記錄的關鍵字與查找關鍵字比較,如果兩者相等,則查找成功;否則利用中間位置記錄將表分成前、後兩個子表,如果中間位置記錄的關鍵字大於查找關鍵字,則進一步查找前一子表,否則進一步查找後一子表。重複以上過程,直到找到符合條件的記錄,使查找成功,或直到子表不存在為止,此時查找不成功。

演算法要求

1、必須採用順序儲存結構。

2、必須依關鍵字大小有序排列。

比較次數

計算公式:

當順序表有n個關鍵字時:

找出失敗時,至少比較a次關鍵字;尋找成功時,最多比較關鍵字次數是b。

注意:a,b,n均為正整數。

說明

折半查找法也稱為二分查找法,它充分利用了元素間的次序關係,採用分治策略,可在最壞的情況下用O(log n)完成搜尋任務。它的基本想法是:(這裡假設數組元素呈升序排列)將n個元素分成個數大致相同的兩半,取a[n/2]與欲查找的x作比較,如果x=a[n/ 2]則找到x,演算法終止;如果xa[n/2],則我們只要在數組a的右半部繼續搜尋x。

更多相關知識,請造訪:PHP中文網

以上是適用於折半查找的表格的儲存方式及元素排列要求為什麼?的詳細內容。更多資訊請關注PHP中文網其他相關文章!

本網站聲明
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn

熱AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智慧驅動的應用程序,用於創建逼真的裸體照片

AI Clothes Remover

AI Clothes Remover

用於從照片中去除衣服的線上人工智慧工具。

Undress AI Tool

Undress AI Tool

免費脫衣圖片

Clothoff.io

Clothoff.io

AI脫衣器

Video Face Swap

Video Face Swap

使用我們完全免費的人工智慧換臉工具,輕鬆在任何影片中換臉!

熱工具

記事本++7.3.1

記事本++7.3.1

好用且免費的程式碼編輯器

SublimeText3漢化版

SublimeText3漢化版

中文版,非常好用

禪工作室 13.0.1

禪工作室 13.0.1

強大的PHP整合開發環境

Dreamweaver CS6

Dreamweaver CS6

視覺化網頁開發工具

SublimeText3 Mac版

SublimeText3 Mac版

神級程式碼編輯軟體(SublimeText3)

熱門話題

Java教學
1653
14
CakePHP 教程
1413
52
Laravel 教程
1306
25
PHP教程
1251
29
C# 教程
1224
24