JavaScript中二分查找的例題詳解
你有沒有碰到過這樣的情況,當刷題的時候,剛開始滿頭霧水不知道從何下手,然后匆匆忙忙的看了題解。哦~是這樣啊,然后開始按照題解的思路答題。答到了一半發(fā)現(xiàn)不會了,又看了看題解,最后終于答出來了??纯戳藢崿F(xiàn)的代碼,一步、兩步、三步、四步···這也不難啊。
突然有一天面試了,問到了你曾刷到的題目,此時你只記得你曾經(jīng)刷過了~。思路全忘了。
我也經(jīng)常碰到這種境況,我也承認我是個算法小菜雞。所以我打算用文章的形式記錄我學習算法的過程。也算是一種輸出吧。有大佬說啊“學習算法就像是做數(shù)學題,記住公式,碰到題目想想是屬于哪一種,開始套公式。”那咱們就試試吧!
二分查找在我們學習算法中是很重要的一部分,而且面試的時候會經(jīng)常的讓我們手寫一些算法。
探究幾個最常用的二分查找場景:尋找一個數(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
寫清楚,這樣可以清楚的展示所有細節(jié)。
Math.floor(left + (right - left) / 2)
其實和Math.floor((left +right)/2)
的結(jié)果是一樣的。如果left
和right
很大的時候,相加會導致移除。Math.floor(left + (right - left) / 2)
可以有效的防止溢出。
尋找一個數(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題二分查找 這題是二分查找最簡單的題型,幾乎所有的二分查找的題型都是根據(jù)這個拓展的。
我們首先考慮的是搜索區(qū)間。因為定義的right
為nums.length - 1
,所以搜索區(qū)間為[left, right]
兩端都閉。當查找到了目標元素,則停止搜索退出循環(huán),然后返回目標值對應的索引。
當沒有找到目標元素,循環(huán)的終止條件為left === right + 1
的時候,直接返回-1即可。
缺陷
如果給你個有序數(shù)組nums = [1,2,2,2,3]
,target
為2,此時用上面的方法返回的索引是2。如果我們想得到的target
的在nums
中最左邊滿足條件的值,或者最右邊滿足條件的值,這種方法就有問題了。
可能會想到,當找到了target
的值,然后向左,向右做線性搜索。但是這樣就很難保證二分查找對數(shù)級的復雜度了。
尋找最左邊滿足條件的值
方式一
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中使用的<
,而不是<=
。因為我們在定義right
的時候,是nums.length
而不是nums.length-1
。那就說明我們的搜索區(qū)間是在[left,right)
左閉右開。所以終止條件就是當left == right
的時候。
還會發(fā)現(xiàn)一個不一樣的地方,right = mid
而不是right = mid - 1
,這個還是受上面的搜索區(qū)間的影響。因為搜索區(qū)間為[left,right)
左閉右開,所以當nums[mid]
被檢測到的時候,下一步應該縮小搜索區(qū)間。當nums[mid] === target
的時候,雖然已經(jīng)找到了target
的值,但是不要立即返回,而是縮小搜索區(qū)間為[left, mid)
。然后不斷的向左邊收縮,直到鎖定左側(cè)邊界,也就是當left == right
的時候。
最后,考慮下越界情況,當left
的值為nums.length
的時候說明查找左側(cè)邊界已經(jīng)超出了搜索區(qū)間,說明target
的值比所有數(shù)都大。當left
的值為target
的時候,說明找到了直接返回即可。然后其實返回left
和返回right
都一樣,因為我們的終止條件是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]
左閉右閉。因為right
的取值為nums.length - 1
是nums
的最后一個值。while
的終止條件則為left == right + 1
,也就是代碼中用的<=
。
此時right = mid - 1
而不是right = mid
, 因為搜索區(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)
左閉右開的方式。關鍵的點在于當nums[mid]=== target
的時候,設置的是left=mid+1
。這樣就可以把搜索區(qū)間變?yōu)?code>[mid+1, right)。利用這種方式不斷的增大左邊界left
的值,是的區(qū)間不斷的向右靠攏,最后到達右邊界。
但是這種方式最后返回的是left - 1
。因為while
的終止條件是left === right
,此時循環(huán)已經(jīng)退出,如果已經(jīng)找到了,那么left
的則比要鎖定的目標索引多1。因為下面這段代碼
if(nums[mid] === target) { left = mid + 1 }
所以最后的目標值要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]
左閉右閉。
其實二分查找差不多也就是這三種情況,你也可以理解為就是一種情況,然后不斷的延伸。那我們記住套路了就開始去刷題鞏固一下吧!
以上就是JavaScript中二分查找的例題詳解的詳細內(nèi)容,更多關于JavaScript二分查找的資料請關注腳本之家其它相關文章!
相關文章
layer彈出框確定前驗證:彈出消息框的方法(彈出兩個layer)
今天小編就為大家分享一篇layer彈出框確定前驗證:彈出消息框的方法(彈出兩個layer),具有很好的參考價值,希望對大家有所幫助。一起跟隨小編過來看看吧2019-09-09JavaScript 獲取當前日期時間 年月日 時分秒的方法
這篇文章主要介紹了JavaScript 獲取當前日期時間年月日時分秒的方法,通過案例代碼介紹了獲取當前日期方法,代碼簡單易懂,需要的朋友可以參考下2023-10-10JavaScript代碼因逗號不規(guī)范導致IE不兼容的問題
這篇文章主要介紹了JavaScript代碼因逗號不規(guī)范導致IE不兼容的問題的相關資料,需要的朋友可以參考下2016-02-02