K60至尊版剛預(yù)熱 一加Ace2 Pro正面硬剛
Redmi這邊剛?cè)缁鹑巛钡男麄髁薑60 Ultra的各種技術(shù)和硬件配置，作為競(jìng)品的一加也坐不住了。一加中國(guó)區(qū)總裁李杰發(fā)布了兩條微博，表示在自家的一加Ace2上早就已經(jīng)采用了和PixelWo
二分查找是一種在有序數(shù)組中查找元素的算法，通過不斷將搜索區(qū)域分成兩半來實(shí)現(xiàn)。你可能在日常生活中已經(jīng)不知不覺地使用了大腦里的二分查找。
最常見的例子是在字典中查找一個(gè)單詞。假設(shè)你想找到“馬拉松”的定義。你不會(huì)從字典的開頭開始查找。你會(huì)打開字典大約在中間位置。如果你在‘T’處，你已經(jīng)過頭了。所以，你會(huì)調(diào)整并分割差距，縮小范圍直到找到“馬拉松”。
這個(gè)逐步排除的過程就是二分查找的要點(diǎn)，但是針對(duì)數(shù)組的情況。
考慮一個(gè)從1到100的數(shù)字?jǐn)?shù)組，你需要在這個(gè)范圍內(nèi)找到一個(gè)特定的數(shù)字，就像玩一個(gè)猜數(shù)游戲。
簡(jiǎn)單的方法是使用一個(gè)簡(jiǎn)單的for循環(huán)——遍歷數(shù)組中的每個(gè)元素直到找到目標(biāo)項(xiàng)。
function findItem(arr, item) { for (let i = 0; i < arr.length; i++) { if (arr[i] === item) { return i; } } return -1; // 未找到項(xiàng)}這個(gè)方法可以找到，但它的時(shí)間復(fù)雜度是O(n)；想象一下，如果你要找的數(shù)在1到1萬億之間。
你可以比線性查找做得更好。
使用二分查找，不是檢查每個(gè)元素，而是從中間開始。如果你要找的數(shù)字更大，你向右走；如果更小，你向左走。
然后呢？你重復(fù)這個(gè)過程。中間，左邊或右邊，縮小可能性直到找到數(shù)字。
function binarySearch(arr, target) { let left = 0; let right = arr.length - 1; while(left <= right) { let mid = Math.floor((left + right) / 2); if(arr[mid] === target) return mid; if(arr[mid] < target) left = mid + 1; else right = mid - 1; } return -1;}它不僅能迅速切入數(shù)據(jù)；時(shí)間復(fù)雜度為O(logN)，比線性搜索快得多。
在空間方面，它是O(1)。不需要額外的存儲(chǔ)空間。
二分查找最常用于數(shù)組，但也可以應(yīng)用于數(shù)據(jù)庫中的有序序列、排序鏈表中的搜索算法，甚至決策過程中可以預(yù)測(cè)和系統(tǒng)地劃分范圍的情況。
重要的是，二分查找只能在排序的項(xiàng)目集合上執(zhí)行。整個(gè)二分查找的方法基于這樣一個(gè)原則，即集合是按順序排列的，這樣算法才能通過比較中間項(xiàng)來預(yù)測(cè)搜索項(xiàng)的位置。如果集合沒有排序，這種預(yù)測(cè)就不起作用，算法也不能正確運(yùn)行。
本文鏈接：http://www.tebozhan.com/showinfo-26-52185-0.html在三分鐘內(nèi)學(xué)習(xí)二分查找
聲明：本網(wǎng)頁內(nèi)容旨在傳播知識(shí)，若有侵權(quán)等問題請(qǐng)及時(shí)與本網(wǎng)聯(lián)系，我們將在第一時(shí)間刪除處理。郵件：2376512515@qq.com
上一篇： Linux下被我誤解的gcc，軟件可執(zhí)行文件的跨系統(tǒng)版本兼容性沒有那么差，如果你也是這樣處理
下一篇： 淺析Apollo配置中心
Copyright ? 2016-2023 天津谷騏科技有限公司 版權(quán)所有 sitemap.xml
違法及侵權(quán)請(qǐng)聯(lián)系：2376512515@qq.com 津ICP備18001702號(hào)
津公網(wǎng)安備 12010102000574號(hào)