你有沒有碰到過這樣的情況，當(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)文章！

最新評(píng)論