二分查找

发表于 更新于 分类于

二分查找的前提为：数组、有序。

逻辑为：优先和数组的中间元素比较，如果等于中间元素，则直接返回。如果不等于则取半继续查找。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
const binarySearch = (arr, target) => {
  let left = 0;
  let right = arr.length - 1;
  
  while(left <= right) {
    let middle = Math.floor((left + right) / 2);
    if(target === arr[middle]) return middle;

    if(target > arr[middle]) {
      left = middle;
    }else {
      right = middle;
    }
  }
  return -1;
}

const arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]
console.log(binarySearch(arr, 10))  // 9