算法|算法-二分查找排序算法|数据结构|算法

二分查找的理解：
二分查找就是一种有序数组中查找某一特定元素的搜索算法
关键词：1. 有序 2. 数组
实现原理：

文章图片

步骤：

查找整个数组中间位置（中间位置1）
判断目标元素5比中间位置元素值大还是小（5<13），所以只需要中间元素左半端进行查找
找1-13元素的中间位置（中间位置2）
判断目标元素位置和中间元素的大小关系，（5=5），搜索停止，返回中间元素下标

代码实现

不存在重复值

function noSame(arr, target) { if (arr.length <= 1) return -1 // 低位下标 let lowIndex = 0 // 高位下标 let highIndex = arr.length - 1while (lowIndex <= highIndex) { // 中间下标 const midIndex = Math.floor((lowIndex + highIndex) / 2) if (target < arr[midIndex]) { highIndex = midIndex - 1 } else if (target > arr[midIndex]) { lowIndex = midIndex + 1 } else { // target === arr[midIndex] return midIndex } } return -1 }

存在重复值

function Same(arr, target) { if (arr.length <= 1) return -1 // 低位下标 let lowIndex = 0 // 高位下标 let highIndex = arr.length - 1while (lowIndex <= highIndex) { // 中间下标 const midIndex = Math.floor((lowIndex + highIndex) / 2) if (target < arr[midIndex]) { highIndex = midIndex - 1 } else if (target > arr[midIndex]) { lowIndex = midIndex + 1 } else { // 当 target 与 arr[midIndex] 相等的时候，如果 midIndex 为0或者前一个数比 target 小那么就找到了第一个等于给定值的元素，直接返回 if (midIndex === 0 || arr[midIndex - 1] < target) return midIndex // 否则高位下标为中间下标减1，继续查找 highIndex = midIndex - 1 } } return -1 }

缺点：
【算法|算法-二分查找】有序：我们很难保证我们的数组都是有序的
数组：数组读取效率是O(1)，可是它的插入和删除某个元素的效率却是O(n)，并且数组的存储是需要连续的内存空间，不适合大数据的情况
应用场景