算法学习(六): 二分搜索

定义

---

从一个简单问题说起

给定一个排序并不存在重复元素的数组: [1,2,5,7,8,9,13], 查找8的位置

暴力解法: 遍历整个数组, 找到与给定值相同的元素, 返回下标, 时间复杂度O(n)

另一种解法:

1. 我们可以先取数组中间位置的值, 看中间位置的值和目标值的大小, 假如中间位置的值大于目标值, 则说明目标值处于数组的中间位置的左半部分, 假如中间位置的值小于目标值, 则说明目标值处于数组中间位置的右半部分
2. 这里我们假设数组中间位置的值大于目标值, 则说明目标值处于数组中间值的左半部分, 那么右半部分我们就不需要再去查找了
3. 对于中间值的左半部分我们继续取中间位置的值, 像上面那样我们继续判断中间位置的值的大小, 大于目标值我们取左半部分, 小于目标值我们取右半部分
4. 按照上面每次去一半的方法一直分下去, 直到数组中的某个位置值与目标值相等, 返回该位置

时间复杂度: 由于我们每次分割都会少掉一半, 所以时间复杂度为O(logn)

二分搜索

上面这种每次取一半搜索的方法就是二分搜索

二分搜索注意事项

• 对输入做异常处理: 数组为空或者数组长度为0
• mid = start + (end - start) / 2 这种表示方法可以防止两个整型值相加时溢出
• 使用迭代而不是递归进行二分查找, 因为工程中递归写法存在潜在溢出的可能
• while终至条件: start + 1 < end而不是start <= end, start == end时可能出现死循环
• 迭代终至时target应为start或者end中的一个。循环终至条件有两个, 具体应看是找到第一个还是最后一个而定

function binarySearch(arr, target) {
  if (arr.length < 1) {
    return -1
  }
  let start = 0
  let end = arr.length - 1
  while (start + 1 < end) {
    let mid = Math.floor(start + (end - start) / 2)
    if (arr[mid] >= target) {
      end = mid
    }else if (arr[mid] < target) {
      start = mid
    }
  }
  
  if (arr[start] === target) {
    return start
  }
  if (arr[end] === target) {
    return end
  }
return -1
}

例题

---

搜索插入位置

给定一个排序数组和一个目标值, 如果在数组中找到了目标值则返回索引。
如果没有, 返回到它将会被按顺序插入的位置。
你可以假设在数组中无重复元素

case1:
输入: [1,3,5,6], 5 输出: 2
case2：
输入: [1,3,5,6], 2 输出: 1
case3:
输入: [1,3,5,6], 7 输出: 4
case4:
输入: [1,3,5,6], 0 输出: 0

分析:

• 在目标值是数组中的数时, 很明显这就是标准的二分搜索的题
• 在目标值不是数组中的数时, 情况分三种情况:
  1. 目标值在数组中某两个数大小之间, 上面题的case2就是这种情况, 这种情况下, 目标值的大小一定是处在数组某相邻两个数之间, 换句话说也就是目标值永远插入在start+1的位置
  2. 目标值比数组起始位置数还小, case4, 这种情况永远返回0
  3. 目标值比数组最后一位的值还大. case3, 此时永远返回arr.length + 1

function searchInsert(arr, target) {
  if (arr.length < 1) {
    return 0
  }
  
  let start = 0
  let end = arr.length - 1
  
  while (start + 1 < end) {
    let mid = Math.floor(start + (end - start) / 2)
    if (arr[mid] < target) {
      start = mid
    } else {
      end = mid
    }
  }
  if (arr[start] === target) {
    return start
  }
  if (arr[end] === target) {
    return end
  }
  if (target > arr[end]) {
    return end + 1
  }
  if (target < arr[start]) {
    return 0
  }
  return start + 1
}

搜索二维矩阵

编写一个高效的算法来搜索m*n矩阵中的一个目标值。
该矩阵具有以下特性:
每行中的整数从左向右排序。
每行的第一个数大于前一行的最后一个整数。

例如:
以下矩阵:
1   2   3   4
5   6   7   8
11 13 15 17
56 78 89 98
给定一个目标值3, 返回下标

分析:

• 由于每一行第一个数都比前一行最后一个数大, 所有这个矩阵转换成一维数组的话, 是一个排好序的一维数组, 这个问题就可以转换成一维数组搜索, 也就是最基本的二维数组问题
• 矩阵每一行4个元素, 第二行第一个matrix[1][0]转换成一维数组时下标为1 * 4 + 0 = 4
  矩阵第三行第二个matrix[2][1]转换成一维数组时下标为 2 * 4 + 1 = 9
  以此类推, matrix[n][m]转换成一维数组时下标为n * 4 + m
  一维数组arr[n]转换成每组有m个数的martix时下标为matrix[n/m][n%m]

function binarySearch(matrix, target) {
  if (matrix.length < 1 || matrix[0].length < 1) {
    return -1
  }
  
  let start = 0
  let end = matrix.length * matrix[0].length - 1

  while (start + 1 < end) {
    let mid = Math.floor(start + (end - start) / 2)
    if (matrix[Math.floor(mid / matrix[0].length)][mid % matrix[0].length] < target) {
      start = mid
    } else {
      end = mid
    }
  }
  if (matrix[Math.floor(start / matrix[0].length)][start % matrix[0].length] === target) {
    return [Math.floor(start / matrix[0].length), start % matrix[0].length]
  }
  if (matrix[Math.floor(end / matrix[0].length)][end % matrix[0].length] === target) {
    return [Math.floor(end / matrix[0].length), end % matrix[0].length]
  }
  return -1
}

求整数的平方根

给定一个整数, 返回它的平方根, 平方根不是整数的, 向下取整
例如:
输入: 25 输出: 5
输入: 0 输出: 0
输入: 9 输出: 3
输入: 7 输出: 2

分析:
这道题可以用二分搜索来做

• 取0到n中间的数m
• m的平方大于n的话说明, n的平方根在0到m之间
• 去0到m中间的值, 继续平方, 如果大于n, 说明n的平方根在0到m/2之间, 如果小于m, 说明在m/2到m之间
• 依次类推, 直到找到结果, 如果分到没办法再分下去还没有找到结果, 则返回最后一次取值范围的左边界

function mySqrt(n) {
 if (n === 0) {
   return 0
 }else if (n < 0) {
   return 'error'
 }
 
 let start = 0
 let end = n
 while (start + 1 < end) {
   let mid = Math.floor(start + (end - start) / 2)
   if (mid * mid < n) {
     start = mid
   } else {
     end = mid
   }
 }
 if (end === n / end) {
   return end
 }
 return start
}