關於Binary Search搜尋方法與示意圖

    AllenLi
    Coding

    Binary search
    Traversal in Binary Tree：

    此搜尋法在數據已排序完成下較適合使用，將陣列中央的數值與目標數值進行比較，
並判斷目標數值在陣列中央的左邊或右邊。因此，每一次比較就縮小一半的搜尋範圍。

    BinarySearch

    Input: nums = [1, 2, 3, 4, 5]

let binarySearch = (nums, target) => {
  let left = 0, right = nums.length -1
  
  while (left <= right) {
    let middleIndex = Math.floor((left+ right) / 2)

    if (nums[middleIndex] === target) {
      return middleIndex
    } else if (nums[middleIndex] > target) {
      right = middleIndex - 1
    } else if (nums[middleIndex] < target) {
      left = middleIndex + 1
    }
  }
  return false
};

console.log(binarySearch([1, 2, 3, 4, 5], 2))

Output: 1

    Flow Chart:

    console.log(middleIndex, left, right)

step.1
(middleIndex, left, right) //(2, 0 ,4)
nums[middleIndex] > target //3 > 2
right = middleIndex - 1 //4 - 1 = 3

step.2
(middleIndex, left, right) //(1, 0 ,3)
nums[middleIndex] === target //2 = 2
return middleIndex = 1

    Related Posts