JavaScript中二分查找的例題詳解
你有沒有碰到過這樣的情況,當(dāng)刷題的時(shí)候,剛開始滿頭霧水不知道從何下手,然后匆匆忙忙的看了題解。哦~是這樣啊,然后開始按照題解的思路答題。答到了一半發(fā)現(xiàn)不會(huì)了,又看了看題解,最后終于答出來了??纯戳藢?shí)現(xiàn)的代碼,一步、兩步、三步、四步···這也不難啊。
突然有一天面試了,問到了你曾刷到的題目,此時(shí)你只記得你曾經(jīng)刷過了~。思路全忘了。
我也經(jīng)常碰到這種境況,我也承認(rèn)我是個(gè)算法小菜雞。所以我打算用文章的形式記錄我學(xué)習(xí)算法的過程。也算是一種輸出吧。有大佬說啊“學(xué)習(xí)算法就像是做數(shù)學(xué)題,記住公式,碰到題目想想是屬于哪一種,開始套公式。”那咱們就試試吧!
二分查找在我們學(xué)習(xí)算法中是很重要的一部分,而且面試的時(shí)候會(huì)經(jīng)常的讓我們手寫一些算法。
探究幾個(gè)最常用的二分查找場(chǎng)景:尋找一個(gè)數(shù)、尋找左側(cè)邊界、尋找右側(cè)邊界
二分查找公式
function binarySearch(nums, target) { let left = 0 let right = ... while(...) { const mid = Math.floor(left + (right - left) / 2) if(nums[mid] === target) { ... } else if(nums[mid] < target) { left = ... } else if(nums[mid] > target) { right = ... } } return ... }
分析二分查找技巧 不要出現(xiàn)else
,而是把所有情況用else if
寫清楚,這樣可以清楚的展示所有細(xì)節(jié)。
Math.floor(left + (right - left) / 2)
其實(shí)和Math.floor((left +right)/2)
的結(jié)果是一樣的。如果left
和right
很大的時(shí)候,相加會(huì)導(dǎo)致移除。Math.floor(left + (right - left) / 2)
可以有效的防止溢出。
尋找一個(gè)數(shù)
var search = function (nums, target) { let left = 0; let right = nums.length - 1; while (left <= right) { const mid = Math.floor(left + (right - left) / 2); if (nums[mid] === target) { return mid; } else if (nums[mid] > target) { right = mid - 1; } else if (nums[mid] < target) { left = mid + 1; } } return -1; };
力扣第704題二分查找 這題是二分查找最簡(jiǎn)單的題型,幾乎所有的二分查找的題型都是根據(jù)這個(gè)拓展的。
我們首先考慮的是搜索區(qū)間。因?yàn)槎x的right
為nums.length - 1
,所以搜索區(qū)間為[left, right]
兩端都閉。當(dāng)查找到了目標(biāo)元素,則停止搜索退出循環(huán),然后返回目標(biāo)值對(duì)應(yīng)的索引。
當(dāng)沒有找到目標(biāo)元素,循環(huán)的終止條件為left === right + 1
的時(shí)候,直接返回-1即可。
缺陷
如果給你個(gè)有序數(shù)組nums = [1,2,2,2,3]
,target
為2,此時(shí)用上面的方法返回的索引是2。如果我們想得到的target
的在nums
中最左邊滿足條件的值,或者最右邊滿足條件的值,這種方法就有問題了。
可能會(huì)想到,當(dāng)找到了target
的值,然后向左,向右做線性搜索。但是這樣就很難保證二分查找對(duì)數(shù)級(jí)的復(fù)雜度了。
尋找最左邊滿足條件的值
方式一
function leftBound(nums, target) { let left = 0; let right = nums.length; while (left < right) { const mid = Math.floor(left + (right - left) / 2); if (nums[mid] === target) { right = mid; } else if (nums[mid] < target) { left = mid + 1; } else if (nums[mid] > target) { right = mid; } } if (left === num.length) return -1; return nums[left] === target ? left : -1; }
上面是一種比較常見的代碼形式。但是和我們剛開始的框架是可以匹配的。在這里while中使用的<
,而不是<=
。因?yàn)槲覀冊(cè)诙xright
的時(shí)候,是nums.length
而不是nums.length-1
。那就說明我們的搜索區(qū)間是在[left,right)
左閉右開。所以終止條件就是當(dāng)left == right
的時(shí)候。
還會(huì)發(fā)現(xiàn)一個(gè)不一樣的地方,right = mid
而不是right = mid - 1
,這個(gè)還是受上面的搜索區(qū)間的影響。因?yàn)樗阉鲄^(qū)間為[left,right)
左閉右開,所以當(dāng)nums[mid]
被檢測(cè)到的時(shí)候,下一步應(yīng)該縮小搜索區(qū)間。當(dāng)nums[mid] === target
的時(shí)候,雖然已經(jīng)找到了target
的值,但是不要立即返回,而是縮小搜索區(qū)間為[left, mid)
。然后不斷的向左邊收縮,直到鎖定左側(cè)邊界,也就是當(dāng)left == right
的時(shí)候。
最后,考慮下越界情況,當(dāng)left
的值為nums.length
的時(shí)候說明查找左側(cè)邊界已經(jīng)超出了搜索區(qū)間,說明target
的值比所有數(shù)都大。當(dāng)left
的值為target
的時(shí)候,說明找到了直接返回即可。然后其實(shí)返回left
和返回right
都一樣,因?yàn)槲覀兊慕K止條件是left == right
。
方式二
function leftBound(nums, target) { let left = 0; let right = nums.length - 1; while (left <= right) { const mid = Math.floor(left + (right - left) / 2); if (nums[mid] < target) { left = mid + 1; } else if (nums[mid] > target) { right = mid - 1; } else if (nums[mid] === target) { right = mid - 1; } } if (left >= nums.length || nums[left] != target) { return -1; } return left; }
方式一的搜索區(qū)間為[left, right)
。我們方式二的搜索區(qū)間改為[left, right]
左閉右閉。因?yàn)?code>right的取值為nums.length - 1
是nums
的最后一個(gè)值。while
的終止條件則為left == right + 1
,也就是代碼中用的<=
。
此時(shí)right = mid - 1
而不是right = mid
, 因?yàn)樗阉鲄^(qū)間變了,[left,right]
兩邊都閉。
最后判斷一下邊界條件,如果left >= nums.length
說明已經(jīng)超出了搜索區(qū)間,或者呢left
的值和target不一樣說明沒找到。
這樣就和第?種?分搜索算法統(tǒng)?了,都是兩端都閉的搜索區(qū)間,?且最后返回的也是left
變量的值。不過我還是比較傾向于這種。哈哈。
尋找最右側(cè)滿足條件的值
方式一
function rightBound(nums, target) { let left = 0; let right = nums.length; while (left < right) { const mid = Math.floor(left + (right - left) / 2); if (nums[mid] === target) { left = mid + 1; } else if (nums[mid] < target) { left = mid + 1; } else if (nums[mid] > target) { right = mid; } } if (left === 0) return -1; return nums[left + 1] === target ? left - 1 : -1; }
這種方式和尋找左側(cè)邊界類似,還是使用搜索區(qū)間為[left, right)
左閉右開的方式。關(guān)鍵的點(diǎn)在于當(dāng)nums[mid]=== target
的時(shí)候,設(shè)置的是left=mid+1
。這樣就可以把搜索區(qū)間變?yōu)?code>[mid+1, right)。利用這種方式不斷的增大左邊界left
的值,是的區(qū)間不斷的向右靠攏,最后到達(dá)右邊界。
但是這種方式最后返回的是left - 1
。因?yàn)?code>while的終止條件是left === right
,此時(shí)循環(huán)已經(jīng)退出,如果已經(jīng)找到了,那么left
的則比要鎖定的目標(biāo)索引多1。因?yàn)橄旅孢@段代碼
if(nums[mid] === target) { left = mid + 1 }
所以最后的目標(biāo)值要left - 1
方式二
function rightBound(nums, target) { let left = 0; let right = nums.length - 1; while (left <= right) { const mid = Math.floor(left + (right - left) / 2); if (nums[mid] === target) { left = mid + 1; } else if (nums[mid] < target) { left = mid + 1; } else if (nums[mid] > target) { right = mid - 1; } } if (right < 0 || nums[right] !== target) { return -1; } return right; }
這里和類似左側(cè)邊界的搜索區(qū)間[left, right]
左閉右閉。
其實(shí)二分查找差不多也就是這三種情況,你也可以理解為就是一種情況,然后不斷的延伸。那我們記住套路了就開始去刷題鞏固一下吧!
以上就是JavaScript中二分查找的例題詳解的詳細(xì)內(nèi)容,更多關(guān)于JavaScript二分查找的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章!
相關(guān)文章
layer彈出框確定前驗(yàn)證:彈出消息框的方法(彈出兩個(gè)layer)
今天小編就為大家分享一篇layer彈出框確定前驗(yàn)證:彈出消息框的方法(彈出兩個(gè)layer),具有很好的參考價(jià)值,希望對(duì)大家有所幫助。一起跟隨小編過來看看吧2019-09-09JavaScript實(shí)現(xiàn)橫向滑出的多級(jí)菜單效果
這篇文章主要介紹了JavaScript實(shí)現(xiàn)橫向滑出的多級(jí)菜單效果,涉及JavaScript數(shù)學(xué)運(yùn)算及頁(yè)面元素樣式動(dòng)態(tài)變換的相關(guān)技巧,具有一定參考借鑒價(jià)值,需要的朋友可以參考下2015-10-10微信小程序?qū)崿F(xiàn)婚禮邀請(qǐng)函全部流程
本文介紹了如何使用微信小程序技術(shù)制作個(gè)性化的婚禮邀請(qǐng)函,包括頁(yè)面布局、交互設(shè)計(jì)和多媒體資源整合,詳細(xì)闡述了從功能需求到頁(yè)面設(shè)計(jì)、測(cè)試優(yōu)化以及發(fā)布流程的全面開發(fā)步驟,通過本項(xiàng)目,可以提升創(chuàng)意設(shè)計(jì)和用戶體驗(yàn)優(yōu)化的能力,需要的朋友可以參考下2024-10-10javascript倒計(jì)時(shí)效果實(shí)現(xiàn)
這篇文章為大家分享了javascript倒計(jì)時(shí)效果實(shí)現(xiàn)代碼段,現(xiàn)今團(tuán)購(gòu)網(wǎng)、電商網(wǎng)、門戶網(wǎng)等,常使用時(shí)間記錄重要的時(shí)刻,如時(shí)間顯示、倒計(jì)時(shí)差、限時(shí)搶購(gòu)等,特別是雙十一活動(dòng),需要的朋友可以參考下2015-11-11JavaScript 獲取當(dāng)前日期時(shí)間 年月日 時(shí)分秒的方法
這篇文章主要介紹了JavaScript 獲取當(dāng)前日期時(shí)間年月日時(shí)分秒的方法,通過案例代碼介紹了獲取當(dāng)前日期方法,代碼簡(jiǎn)單易懂,需要的朋友可以參考下2023-10-10JavaScript代碼因逗號(hào)不規(guī)范導(dǎo)致IE不兼容的問題
這篇文章主要介紹了JavaScript代碼因逗號(hào)不規(guī)范導(dǎo)致IE不兼容的問題的相關(guān)資料,需要的朋友可以參考下2016-02-02