一個運用二分查找演算法的程式的時間複雜度是「對數等級」。二分查找是一種效率較高的查找方法,演算法複雜度即是while迴圈的次數,時間複雜度可以表示「O(h)=O(log2n)」。
本教學操作環境:windows7系統、Dell G3電腦。
一個運用二分查找演算法的程式的時間複雜度是「對數層級」。
相關推薦:《程式設計學習》
二分查找也稱為折半查找(Binary Search),它是一種效率較高的查找方法。但是,折半查找要求線性表必須採用順序儲存結構,且表格中元素依關鍵字有序排列。
查找過程:
首先,假設表中元素是按升序排列,將表中間位置記錄的關鍵字與尋找關鍵字比較,如果兩者相等,則查找成功;否則利用中間位置記錄將表分成前、後兩個子表,如果中間位置記錄的關鍵字大於查找關鍵字,則進一步查找前一子表,否則進一步查找後一子表。重複以上過程,直到找到符合條件的記錄,使查找成功,或直到子表不存在為止,此時查找不成功。
演算法複雜度:
二分查找的基本想法是將n個元素分成大致相等的兩部分,取a[n/2]與x做比較,如果x=a[n/2],則找到x,演算法中止;如果xa[n/2] ,則只要在陣列a的右半部搜尋x.
時間複雜度即是while循環的次數。
總共有n個元素,
漸漸跟下去就是n,n/2,n/4,....n/2^k(接下來運算元素的剩餘個數),其中k就是循環的次數
由於你n/2^k取整後>=1
即令n/2^k=1
可得k=log2n,(是以2為底,n的對數)
所以時間複雜度可以表示O(h)=O(log2n)
下面提供一段二分查找實現的偽代碼:
BinarySearch(max,min,des) mid-<(max+min)/2 while(min<=max) mid=(min+max)/2 if mid=des then return mid elseif mid >des then max=mid-1 else min=mid+1 return max
折半查找法也稱為二分查找法,它充分利用了元素間的次序關係,採用分治策略,可在最壞的情況下用O (log n)完成搜尋任務。它的基本想法是:(這裡假設數組元素呈升序排列)將n個元素分成個數大致相同的兩半,取a[n/2]與欲查找的x作比較,如果x=a[n/ 2]則找到x,演算法終止;如果xa[n/2],則我們只要在數組a的右半部繼續搜尋x。
想要查閱更多相關文章,請造訪PHP中文網! !
以上是一個運用二分查找演算法的程式的時間複雜度是什麼的詳細內容。更多資訊請關注PHP中文網其他相關文章!

如何使用C#编写二分查找算法二分查找算法是一种高效的查找算法,它在有序数组中查找特定元素的位置,时间复杂度为O(logN)。在C#中,我们可以通过以下几个步骤来编写二分查找算法。步骤一:准备数据首先,我们需要准备一个已经排好序的数组作为查找的目标数据。假设我们要在数组中查找特定元素的位置。int[]data={1,3,5,7,9,11,13

我们知道二分查找方法是一种最适合和有效的排序算法。这个算法适用于已排序的序列。算法很简单,它只是从中间找到元素,然后将列表分成两部分,并向左子列表或右子列表移动。我们知道它的算法。现在我们将看到如何在多线程环境中使用二分查找技术。线程的数量取决于系统中存在的核心数。让我们看一下代码以了解思路。示例#include<iostream>#defineMAX16#defineMAX_THREAD4usingnamespacestd;//placearr,keyandothervariabl

C编程语言提供了两种搜索技术。它们如下所示:线性搜索二分搜索二分搜索这种方法只适用于有序列表。给定列表被分成两个相等的部分。给定的关键字与列表的中间元素进行比较。在这里,可能会发生三种情况,如下所示:如果中间元素与关键字匹配,则搜索将在此成功结束如果中间元素大于关键字,则搜索将在左侧分区进行。如果中间元素小于关键字,则搜索将在右侧分区进行。输入(i/p)-未排序的元素列表,关键字。输出(o/p)-成功-如果找到关键字失败-否则key=20mid=(low+high)/2程序1以下是使用二分查找在

如何使用Java实现二分查找算法二分查找算法是一种高效的查找方法,适用于已排序的数组。它的基本思想是不断缩小查找范围,将查找值与数组中间的元素进行比较,并根据比较结果决定继续查找左半部分还是右半部分,直到找到目标元素或查找范围缩小为空。下面我们来具体介绍如何用Java实现二分查找算法。步骤一:实现二分查找方法publicclassBinarySearch

如何使用Python实现二分查找算法?二分查找算法,也称为折半查找算法,是一种高效的查找算法。它适用于有序的数组或列表,通过将目标值与数组中间位置的元素进行比较,从而缩小查找范围。下面将介绍如何在Python中实现二分查找算法,并提供具体的代码示例。算法思路:将目标值与数组中间位置的元素进行比较;如果相等,则返回元素位置;如果目标值大于中间位置的元素,则在右

立方根是一个整数值,当它自己连续乘以自己三次时,得到原始数值。在本文中,我们将编写一个使用二分搜索来找到一个数的立方根的Java程序。找到一个数的立方根是二分搜索算法的一个应用之一。在本文中,我们将详细讨论如何使用二分搜索来计算立方根。输入-输出示例Example-1:Input:64Output:4如,64的立方根为4,输出为4。Example-2:Input:216Output:6如,216的立方根为6,输出为6。二分查找二分搜索是一种用于查找元素(即排序数组中的键)的算法。二进制算法的工作

在这个问题中,我们得到了一个有理数的排序数组。我们必须使用二分搜索算法来搜索该有理数数组的给定元素,而不使用浮点运算。有理数是以p/q形式表示的数字,其中p和q都是整数。例如,⅔、⅕。二分搜索是一种搜索技术,通过查找数组的中间来查找元素。用于查找使用二分法搜索有理数排序数组中的元素,其中不允许浮点运算。我们将比较分子和分母,以找出哪个元素更大或哪个元素是要找到的元素。示例让我们为此创建一个程序,#include<stdio.h>structRational{ &am

PHP算法解析:如何使用二分查找算法在有序数组中快速定位元素?概述:二分查找算法是一种高效的查找算法,它适用于有序数组中查找特定元素。本文将详细介绍二分查找算法的原理,并给出PHP代码示例。原理:二分查找算法通过反复将查找范围缩小一半,从而快速定位目标元素。其流程如下:首先,将查找范围缩小为数组的开头和结尾;然后,计算中间元素的索引,将其与目标元素进行比较;

熱AI工具

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

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

Undress AI Tool
免費脫衣圖片

Clothoff.io
AI脫衣器

AI Hentai Generator
免費產生 AI 無盡。

熱門文章

熱工具

SublimeText3 英文版
推薦:為Win版本,支援程式碼提示!

SecLists
SecLists是最終安全測試人員的伙伴。它是一個包含各種類型清單的集合,這些清單在安全評估過程中經常使用,而且都在一個地方。 SecLists透過方便地提供安全測試人員可能需要的所有列表,幫助提高安全測試的效率和生產力。清單類型包括使用者名稱、密碼、URL、模糊測試有效載荷、敏感資料模式、Web shell等等。測試人員只需將此儲存庫拉到新的測試機上,他就可以存取所需的每種類型的清單。

Dreamweaver Mac版
視覺化網頁開發工具

SAP NetWeaver Server Adapter for Eclipse
將Eclipse與SAP NetWeaver應用伺服器整合。

SublimeText3 Linux新版
SublimeText3 Linux最新版