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

JavaScript中二分查找的例題詳解

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

你有沒有碰到過這樣的情況,當(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é)果是一樣的。如果leftright很大的時(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的rightnums.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 - 1nums的最后一個(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)

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

    JavaScript實(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
  • ES6學(xué)習(xí)之變量的兩種命名方法示例

    ES6學(xué)習(xí)之變量的兩種命名方法示例

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

    原生JS進(jìn)行前后端同構(gòu)

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

    微信小程序?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-10
  • javascript倒計(jì)時(shí)效果實(shí)現(xiàn)

    javascript倒計(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-11
  • uniapp中如何修改圖標(biāo)和名稱

    uniapp中如何修改圖標(biāo)和名稱

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

    JavaScript 獲取當(dāng)前日期時(shí)間 年月日 時(shí)分秒的方法

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

    JavaScript 中this指向問題案例詳解

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

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

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

最新評(píng)論