Binary search
Traversal in Binary Tree:
此搜尋法在數據已排序完成下較適合使用,將陣列中央的數值與目標數值進行比較, 並判斷目標數值在陣列中央的左邊或右邊。因此,每一次比較就縮小一半的搜尋範圍。
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