二分搜索各种情况总结

2024-02-26 12:01:52

1. 基本的二分搜索(递归实现)

问题：查找目标元素，存在返回索引，不存在返回 -1
```
let array = [1,2,3,4,5,6,7] 

target = 3
```
搜索范围：[ l, r ]
递归的终止条件：
```
l > r
```

递归代码：

function BinarySearch(arr, l, r, target) {

  if (l > r) return -1 // 递归的终止条件

  let mid = Math.floor(l + (r - l) / 2)

  if (arr[mid] === target) return mid
  if (arr[mid] < target) {
    return BinarySearch(arr, mid + 1, r, target)
  }
  return BinarySearch(arr, l, mid - 1, target)
}

let array = [1, 2, 3, 4, 5, 6, 7]

console.log(BinarySearch(array, 0, array.length - 1, 1)); // 0
console.log(BinarySearch(array, 0, array.length - 1, 3)); // 2

2. 基本的二分搜索（非递归实现）

循环的终止条件：

l > r （此时查找的区间为空区间）

搜索范围：

在 arr[l, r]范围内查找 target(变成空区间的时候退出循环)

非递归代码：

/*
 * @Description: 二分搜索的非递归实现
 * @Autor: zhangbing
 * @Date: 2021-09-19 11:43:30
 * @LastEditors: zhangbing
 * @LastEditTime: 2021-09-19 11:54:17
 */

function binarySearch(arr, target) {
  let l = 0
  let r = arr.length - 1

  // 在 arr[l, r]范围内查找 target(变成空区间的时候退出循环)
  while (l <= r) {
    let mid = Math.floor(l + (r - l) / 2)
    if (arr[mid] === target) return mid
    if (arr[mid] < target) {
      l = mid + 1
    } else {
      r = mid - 1
    }
  }

  return -1
}

let array = [1, 2, 3, 4, 5, 6]
console.log(binarySearch(array, 2)); // 1
console.log(binarySearch(array, 7)); // -1

3. 二分搜索另一种方式的区间范围

循环的终止条件

l == r (因为左闭右开， 因此此时为空区间)

搜索范围：

在 arr[l, r) 的范围内查找 target

代码：

/*
 * @Description: 二分搜索另一种方式的区间范围
 * @Autor: zhangbing
 * @Date: 2021-09-19 12:05:45
 * @LastEditors: zhangbing
 * @LastEditTime: 2021-09-19 13:56:04
 */
function binarySearch(arr, target) {
  let l = 0
  let r = arr.length // 右边开区间

  // 在 arr[l, r) 的范围内查找 target
  while(l < r) {
    let mid = Math.floor(l + (r - l) / 2) 
    if(arr[mid] === target) return mid
    if(arr[mid] < target) {
      l = mid + 1 // 继续在 arr[mid+1, r) 范围内寻找解
    } else {
      r = mid // 继续在 data[l, mid) 范围内寻找解
    }
  }

  return -1
}

let array = [1,2,3,4,5,6]
console.log(binarySearch(array, 2)) // 1
console.log(binarySearch(array, 7)) // -1

4. upper 问题

问题：

查找大于 target 的最小值（索引）

搜索范围：
```
在 arr[l,r) 的范围内查找
```

代码：

/*
 * @Description: 查找大于 target 的最小值（upper问题）
 * @Autor: zhangbing
 * @Date: 2021-09-19 12:41:50
 * @LastEditors: zhangbing
 * @LastEditTime: 2021-09-19 13:00:49
 */

function binarySearch(arr, target) {
  let l = 0
  let r = arr.length // 因为大于target的最小值的索引可能超过数组的最大索引
  // 在 arr[l,r) 的范围内查找
  while (l < r) {
    let mid = Math.floor(l + (r - l) / 2)
    if (arr[mid] > target) {
      r = mid
    } else {
      l = mid + 1
    }
  }
  return l // 或者 r 也可以，因为此时 l === r
}

let array = [23, 56, 65, 69, 72, 89, 96, 99]
console.log(binarySearch(array, 60)); // 2
console.log(binarySearch(array, 10)); // 0
console.log(binarySearch(array, 100)); // 8

let arr = [1,2,3,3,5,5]
console.log(binarySearch(arr, 4)); // 4
console.log(binarySearch(arr, 3)); // 4

5. ceil 问题

问题：

若数组中不存在 target，返回 upper
若数组中存在 target，返回最大索引（可能存在多个相同的值，返回最后一个值的索引）
搜索范围：

因为不存在需返回 upper，可能超出数字的最后一个元素的索引
所以搜索范围为：arr[l, r)

代码：

/*
 * @Description: 如果数组中存在元素，返回最大索引；如果数组中不存在元素，返回 upper（大于target的最小值的索引）
 * @Autor: zhangbing
 * @Date: 2021-09-19 13:11:35
 * @LastEditors: zhangbing
 * @LastEditTime: 2021-09-19 13:24:18
 */

function binarySearch_ceil(arr, target) {
  let l = 0
  let r = arr.length
  while (l < r) {
    let mid = Math.floor(l + (r - l) / 2)
    if (arr[mid] > target) {
      r = mid
    } else {
      l = mid + 1
    }
  }
	
  // 上述代码得到的 l === r (upper的情况)
  // 判断数组是否存在 target（若存在 target ，则必然是 arr[l] 的前一个元素）
  return arr[l - 1] === target ? l - 1 : l
}

let array = [1, 1, 3, 3, 5, 5, 7, 7]
console.log(binarySearch_ceil(array, 5)); // 5
console.log(binarySearch_ceil(array, 6)); // 6 
console.log(binarySearch_ceil(array, 8)); // 8

6. lower_ceil

问题：

大于等于 target 的最小索引

/*
 * @Description: 大于等于 target 的最小索引
 * @Autor: zhangbing
 * @Date: 2021-09-19 13:23:50
 * @LastEditors: zhangbing
 * @LastEditTime: 2021-09-19 21:54:11
 */

function binarySearch_lower_ceil(arr, target) {
  let l = 0
  let r = arr.length
  while (l < r) {
    let mid = Math.floor(l + (r - l) / 2)
    if (arr[mid] < target) {
      l = mid + 1
    } else {
      r = mid
    }
  }

  return l
}

let array = [1,1,3,3,5,5,7,7]
console.log(binarySearch_lower_ceil(array, 6)); // 6
console.log(binarySearch_lower_ceil(array, 5)); // 4
console.log(binarySearch_lower_ceil(array, 1)); // 0
console.log(binarySearch_lower_ceil(array, 8)); // 8

let array1 = [1,2,3,5,5,7,8]
console.log(binarySearch_lower_ceil(array1, 5)); // 3
console.log(binarySearch_lower_ceil(array1, 6)); // 5

7. lower

问题：

lower: 查找小于 target 的最大值 (注意死循环问题，调整 mid 上取整)

代码：

/*
 * @Description: lower: 查找 小于 target 的最大值 (注意死循环问题，调整 mid 上取整)
 * @Autor: zhangbing
 * @Date: 2021-09-19 14:10:35
 * @LastEditors: zhangbing
 * @LastEditTime: 2021-09-19 14:32:07
 */

function binarySearch_lower(arr, target) {
  let l = -1
  let r = arr.length - 1
  // 在 arr[l, r] 范围内寻找
  while (l < r) {
    let mid = Math.floor(l + (r - l) / 2) + 1 // 当 l 与 r 相邻时取右边界（上取整）
    if (arr[mid] < target) {
      l = mid
    } else {
      r = mid - 1
    }
  }

  return l
}

let array = [1, 1, 3, 3, 5, 5]
console.log(binarySearch_lower(array, 3)) // 1
console.log(binarySearch_lower(array, 1)) // -1
console.log(binarySearch_lower(array, 5)) // 3
console.log(binarySearch_lower(array, 6)) // 5

let array1 = [1,3,5,7]
console.log(binarySearch_lower(array1, 6)) // 2
console.log(binarySearch_lower(array1, 0)) // -1
console.log(binarySearch_lower(array1, 9)) // 3
console.log(binarySearch_lower(array1, 5)) // 1

注意：

当 l = 0, r = 1 时，此时 mid 计算为 0，arr[mid] < target, l 会始终等于0，此时程序会陷入死循环。为避免这种情况， mid 设置为向上取整。

8. lower_floor

问题：

lower_floor : 如果数组中存在元素，返回最小索引；如果不存在，返回 lower（小于 target 的最大值的索引）

代码：

/*
 * @Description: lower_floor : 如果数组中存在元素，返回最小索引；如果不存在，返回 lower（小于 target 的最大值的索引）
 * @Autor: zhangbing
 * @Date: 2021-09-19 14:34:46
 * @LastEditors: zhangbing
 * @LastEditTime: 2021-09-19 22:33:05
 */

function binarySearch_lower_floor(arr, target) {
  let l = -1
  let r = arr.length - 1
  while (l < r) {
    let mid = Math.floor(l + (r - l) / 2) + 1
    if (arr[mid] < target) {
      l = mid
    } else {
      r = mid - 1
    }
  }

  if (arr[l + 1] !== target) {
    return l
  } else {
    return l + 1
  }


}

let array = [1, 1, 3, 3, 5, 5]
console.log(binarySearch_lower_floor(array, 3)); // 2
console.log(binarySearch_lower_floor(array, 4)); // 3
console.log(binarySearch_lower_floor(array, 6)); // 5

let array1 = [1,3,5,7,9]
console.log(binarySearch_lower_floor(array1, 3)); // 1
console.log(binarySearch_lower_floor(array1, 4)); // 1
console.log(binarySearch_lower_floor(array1, 0)); // -1
console.log(binarySearch_lower_floor(array1, 10)); // 4

9. upper_floor

问题：

如果数组中存在元素，返回最大索引；如果数组中不存在元素，返回 lower（小于 target 的最大值的索引）

代码：

/*
 * @Description: 如果数组中存在元素，返回最大索引；如果数组中不存在元素，返回 lower
 * @Autor: zhangbing
 * @Date: 2021-09-19 14:37:46
 * @LastEditors: zhangbing
 * @LastEditTime: 2021-09-19 22:47:03
 */

/** <= target 的最大索引
 * [1,1,3,3,5,5]
 * 如果查找 5，返回 5
 * 如果查找 4，返回 3
 */

function binarySearch_upper_floor(arr, target) {
  let l = -1
  let r = arr.length - 1
  while(l < r) {
    let mid = Math.floor(l + (r - l) / 2) + 1
    if(arr[mid] < target) {
      l = mid
    } else {
      r = mid - 1
    }
  }

  // console.log(l) // 3 3

  if(arr[l + 1] !== target) {
    return l
  } else {
    while(arr[l+1] === target) {
      l++
    }
    return l
  }
}

let array = [1,1,3,3,5,5]
console.log(binarySearch_upper_floor(array, 5)) // 5
console.log(binarySearch_upper_floor(array, 4)) // 3
console.log(binarySearch_upper_floor(array, 6)) // 5

let array1 = [1,3,5,7,9]
console.log(binarySearch_upper_floor(array1, 3)); // 1
console.log(binarySearch_upper_floor(array1, 4)); // 1
console.log(binarySearch_upper_floor(array1, 0)); // -1
console.log(binarySearch_upper_floor(array1, 10)); // 4

码农公寓

二分搜索各种情况总结

目录

1. 基本的二分搜索(递归实现)

2. 基本的二分搜索（非递归实现）

3. 二分搜索另一种方式的区间范围

4. upper 问题

5. ceil 问题

6. lower_ceil

7. lower

8. lower_floor

9. upper_floor

码农公寓

目录

1. 基本的二分搜索(递归实现)

2. 基本的二分搜索（非递归实现）

3. 二分搜索另一种方式的区间范围

4. upper 问题

5. ceil 问题

6. lower_ceil

7. lower

8. lower_floor

9. upper_floor

相关文章