二分查找

[maicFir]

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

前段时间加了一个刷算法题的群，也刷了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

总结

1、二分查找，将数组一分为二，确认中间位置，确定元素所在区域范围，如果是在左区间，则右区间则是mid - 1,左区间则固定[left, mid -1]，如果元素所在区域是右区间，那么确定是右区间，右区间固定，左区间则是mid+1,[mid+1,right]

2、使用原生提供的findIndex快速寻找目标元素下标位置，最简单的一种方式

3、擅用map移花接木，利用map设置值方式,将元素值与索引存在map中，从而找到目标索引

4、利用对象存取数据，将元素值与索引存在result中，根据target从而找到目标索引

5、二分查找部分代码参考代码随想录[1]

参考资料

[1]代码随想录: https://www.programmercarl.com/0704.%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE.html#\_704-%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE