欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

JavaScript中二分查找的例題詳解

 更新時間:2023年03月09日 08:24:03   作者:翰玥  
二分查找在我們學習算法中是很重要的一部分,而且面試的時候會經(jīng)常的讓我們手寫一些算法。所以這篇文章將通過三個場景帶大家深入了解二分查找算法

你有沒有碰到過這樣的情況,當刷題的時候,剛開始滿頭霧水不知道從何下手,然后匆匆忙忙的看了題解。哦~是這樣啊,然后開始按照題解的思路答題。答到了一半發(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é)果是一樣的。如果leftright很大的時候,相加會導致移除。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ū)間。因為定義的rightnums.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 - 1nums的最后一個值。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)

    今天小編就為大家分享一篇layer彈出框確定前驗證:彈出消息框的方法(彈出兩個layer),具有很好的參考價值,希望對大家有所幫助。一起跟隨小編過來看看吧
    2019-09-09
  • JavaScript實現(xiàn)橫向滑出的多級菜單效果

    JavaScript實現(xiàn)橫向滑出的多級菜單效果

    這篇文章主要介紹了JavaScript實現(xiàn)橫向滑出的多級菜單效果,涉及JavaScript數(shù)學運算及頁面元素樣式動態(tài)變換的相關技巧,具有一定參考借鑒價值,需要的朋友可以參考下
    2015-10-10
  • ES6學習之變量的兩種命名方法示例

    ES6學習之變量的兩種命名方法示例

    最近在學習ES,所以想著將自己學習的一些經(jīng)驗技巧總結(jié)一下,方便學習,所以下面這篇文章主要跟大家分享介紹了關于ES6學習之變量的兩種命名方法,文中通過示例代碼介紹的很詳細,需要的朋友們下面來一起看看吧。
    2017-07-07
  • 原生JS進行前后端同構

    原生JS進行前后端同構

    本文通過實例給大家分享了原生JS進行前后端同構的相關知識點以及相關代碼,有需要的朋友參考學習下。
    2018-04-04
  • 微信小程序?qū)崿F(xiàn)婚禮邀請函全部流程

    微信小程序?qū)崿F(xiàn)婚禮邀請函全部流程

    本文介紹了如何使用微信小程序技術制作個性化的婚禮邀請函,包括頁面布局、交互設計和多媒體資源整合,詳細闡述了從功能需求到頁面設計、測試優(yōu)化以及發(fā)布流程的全面開發(fā)步驟,通過本項目,可以提升創(chuàng)意設計和用戶體驗優(yōu)化的能力,需要的朋友可以參考下
    2024-10-10
  • javascript倒計時效果實現(xiàn)

    javascript倒計時效果實現(xiàn)

    這篇文章為大家分享了javascript倒計時效果實現(xiàn)代碼段,現(xiàn)今團購網(wǎng)、電商網(wǎng)、門戶網(wǎng)等,常使用時間記錄重要的時刻,如時間顯示、倒計時差、限時搶購等,特別是雙十一活動,需要的朋友可以參考下
    2015-11-11
  • uniapp中如何修改圖標和名稱

    uniapp中如何修改圖標和名稱

    這篇文章主要給大家介紹了關于uniapp中如何修改圖標和名稱的相關資料,uni-app是一個使用Vue.js開發(fā)跨平臺應用的前端框架,文中通過圖文介紹的非常詳細,需要的朋友可以參考下
    2023-08-08
  • JavaScript 獲取當前日期時間 年月日 時分秒的方法

    JavaScript 獲取當前日期時間 年月日 時分秒的方法

    這篇文章主要介紹了JavaScript 獲取當前日期時間年月日時分秒的方法,通過案例代碼介紹了獲取當前日期方法,代碼簡單易懂,需要的朋友可以參考下
    2023-10-10
  • JavaScript 中this指向問題案例詳解

    JavaScript 中this指向問題案例詳解

    這篇文章主要介紹了JavaScript 中this指向問題案例詳解,本篇文章通過簡要的案例,講解了該項技術的了解與使用,以下就是詳細內(nèi)容,需要的朋友可以參考下
    2021-08-08
  • JavaScript代碼因逗號不規(guī)范導致IE不兼容的問題

    JavaScript代碼因逗號不規(guī)范導致IE不兼容的問題

    這篇文章主要介紹了JavaScript代碼因逗號不規(guī)范導致IE不兼容的問題的相關資料,需要的朋友可以參考下
    2016-02-02

最新評論