当前位置：网站首页>彻底掌握二分查找

彻底掌握二分查找

2022-07-28 12:49:00 【Maic】

虽然平时业务接触算法不多，但是公司对于程序员的算法要求越来越高，基础不牢，地动山摇，优秀的程序员，算法是核心竞争力，也是解决复杂问题的一种必要手段。

前段时间加了一个刷算法题的群，也刷了leetcode的一些题目，今天一起学习掌握二分查找，熟记于心，触类旁通，达到真正掌握每种解题的方法，希望你在实际业务中有所帮助和思考。

正文开始...

二分查找

题目：给定一个有序无重复的数组arr和目标元素target,返回数组arr中target元素的下标位置

思路：在[left, right]区间中查找，指定中间位置与目标元素进行比较，如果目标元素在中间元素的左边，那么右侧区间就是[left,mid -1],如果目标元素在中间元素的右边，那么就从左侧区间开始[mid+1, right],直至找到与目标元素返回mid为止。

function binarySearch(arr, target) {
  let left = 0; // 数组第一个位置
  let right = arr.length -1; // 数组中最后一个位置
  // [left, right] 区间查找
  while(left <= right) {
    // 取数组中间位置
    let mid = left + Math.floor((right - left) / 2);
    // 目标元素在中间位置的左边
    if (target < arr[mid]) {
      right = mid - 1; // [left, mid-1]
    } else if (target > arr[mid]) {
      // 目标元素在中间元素的右边，那么左区间[mid+1,right]
      left = mid + 1;
    } else {
      return mid // 直到找到target,相等就直接返回mid中间下标位置
    }
  }
  return -1; // 没有找到就返回-1
}
binarySearch([1,3,4,5,7,8], 3); // 1

用一张流程图描述一下上面的一段代码

接下来再看下具体过程

我们会发现，二分查找实际上是从中间位置开始的，如果目标值在中间位置的左边，不断的减少right区间，直至找到mid = right -1,当目标值target=3时，那么就返回mid的下标位置。

还有一种是左闭右开[left,right)

function binarySearch(arr, target) {
  let left = 0; // 数组第一个位置
  let right = arr.length -1; // 数组中最后一个位置
  // [left,right) 区间查找
  while(left < right) {
    // 取数组中间位置
    let mid = left + Math.floor((right - left) / 2);
    // 目标元素在中间位置的左边
    if (target < arr[mid]) {
      right = mid; // [left, mid]
    } else if (target > arr[mid]) {
      // 目标元素在中间元素的右边，那么左区间[mid+1,right]
      left = mid + 1;
    } else {
      return mid // 直到找到target,相等就直接返回mid中间下标位置
    }
  }
  return -1; // 没有找到就返回-1
}
binarySearch([1,3,4,5,7,8], 3);

findIndex

巧用数组提供的api找到匹配的索引

function binarySearch(arr, target) {
  return arr.findIndex(v => v === target)
}
binarySearch([1,3,4,5,7,8], 3); // 1

你会发现原生提供的findIndex无论数组中是否有序，还是无序都可以找到target的索引,但是findIndex也有缺陷，如果数组中有重复的值，那么只会返回第一个先找到的下标索引。

暴力for循环找索引

function binarySearch(arr = [], target) {
  let index = target ? 0 : -1;
  for (let i =0;i< arr.length;i++) {
    if (target === arr[i]) {
      index = i;
      break;
    } else {
      index = -1;
    }
  }
  return index;
}
binarySearch([1,3,4,5,7,8], 3); // 1

巧用map，移花接木

map这种方式的缺陷是数组中不能有重复的值，只是针对无重复的数组

function binarySearch(arr = [], target) {
    const map = new Map();
    arr.forEach((v, index) => {
      map.set(v, index); // 将值设置成map的key
    });
    return map.has(target) ? map.get(target) : -1
}
binarySearch([1,3,4,5,7,8], 3); // 1

借用对象

只针对无重复数组

function binarySearch(arr = [], target) {
    const result = {};
    arr.forEach((v, index) => {
      result[v] = index; // 将值设置成map的key
    });
    return Reflect.has(result, target) ?  result[target]: -1
}
binarySearch([1,3,4,5,7,8], 3); // 1