JavaScript中的二分查找法怎么使用

這篇文章主要介紹“JavaScript中的二分查找法怎么使用”的相關(guān)知識，小編通過實際案例向大家展示操作過程，操作方法簡單快捷，實用性強，希望這篇“JavaScript中的二分查找法怎么使用”文章能幫助大家解決問題。

二分查找公式

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很大的時候，相加會導(dǎo)致移除。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]兩端都閉。當(dāng)查找到了目標元素，則停止搜索退出循環(huán)，然后返回目標值對應(yīng)的索引。

當(dāng)沒有找到目標元素，循環(huán)的終止條件為left === right + 1的時候，直接返回-1即可。

缺陷

如果給你個有序數(shù)組nums = [1,2,2,2,3],target為2，此時用上面的方法返回的索引是2。如果我們想得到的target的在nums中最左邊滿足條件的值，或者最右邊滿足條件的值，這種方法就有問題了。

可能會想到，當(dāng)找到了target的值，然后向左，向右做線性搜索。但是這樣就很難保證二分查找對數(shù)級的復(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中使用的<，而不是<=。因為我們在定義right的時候，是nums.length而不是nums.length-1。那就說明我們的搜索區(qū)間是在[left,right)左閉右開。所以終止條件就是當(dāng)left == right的時候。

還會發(fā)現(xiàn)一個不一樣的地方，right = mid而不是right = mid - 1，這個還是受上面的搜索區(qū)間的影響。因為搜索區(qū)間為[left,right)左閉右開,所以當(dāng)nums[mid]被檢測到的時候，下一步應(yīng)該縮小搜索區(qū)間。當(dāng)nums[mid] === target的時候，雖然已經(jīng)找到了target的值，但是不要立即返回，而是縮小搜索區(qū)間為[left, mid)。然后不斷的向左邊收縮，直到鎖定左側(cè)邊界，也就是當(dāng)left == right的時候。

最后，考慮下越界情況，當(dāng)left的值為nums.length的時候說明查找左側(cè)邊界已經(jīng)超出了搜索區(qū)間，說明target的值比所有數(shù)都大。當(dāng)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)左閉右開的方式。關(guān)鍵的點在于當(dāng)nums[mid]=== target的時候，設(shè)置的是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]左閉右閉。

關(guān)于“JavaScript中的二分查找法怎么使用”的內(nèi)容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識，可以關(guān)注億速云行業(yè)資訊頻道，小編每天都會為大家更新不同的知識點。