大数据面试题十四 · 数据结构与算法 · 二分查找
点击关注上方“知了小巷”，
设为“置顶或星标”，第一时间送达干货。
大数据面试题十四 · 数据结构与算法 · 二分查找
二分查找
基础
用途：针对Sorted（排好序的）数组查找目标值的算法
时间复杂度：O(log(n))
空间复杂度：O(1)
二分查找算法的前置条件是要有一个已经Sorted好的序列，这样在查找所要查找的元素时，首先与序列中间的元素进行比较，如果大于mid这个元素，就在当前序列的后半部分继续查找，如果小于mid这个元素，就在当前序列的前半部分继续查找，直到找到相同的元素，或者所查找的序列范围为空为止。
伪代码:
left = 0, right = n -1
while (left <= right)
// 直接左右相加除以2
mid = (left + right) / 2
case
x[mid] < t: left = mid + 1;
x[mid] = t: p = mid; break;
x[mid] > t: right = mid -1;
return -1;
Python代码实现：
def binarySearch(arr, target):
l , r = 0, len(arr) - 1
while l <= r:
mid = (l + r) // 2
if arr[mid] == target:
return mid
if target > arr[mid]:
l = mid + 1
elif target < arr[mid]:
r = mid - 1
return -1
进一步深入
二分查找：思路很简单，细节是魔鬼。
到底要给mid加1还是减1，while里到底用<=还是<。
常用的二分查找场景：寻找一个数、寻找左侧边界、寻找右侧边界。
模板代码如下：
int binarySearch(int[] nums, int target) {
int left = 0, right = ...;
while(...) {
// 计算mid时需要防止溢出
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
...
} else if (target > nums[mid]) {
left = ...
} else if (target < nums[mid]) {
right = ...
}
}
return ...;
}
-
mid溢出问题
比如left=1, right=Intager的最大值，JDK8：
public class CC {
public static void main(String[] args) {
int left = 1;
int right = Integer.MAX_VALUE;
int mid = (left + right) / 2;
// 输出结果，结果溢出变成负数：
// -1073741824
// - (Integer.MAX_VALUE / 2 + 1)
// Integer.MIN_VALUE / 2
System.out.println(mid);
}
}
python3的sys.maxsize没有类似的问题，int类型可以无限放大：
import sys
left = 1
right = sys.maxsize
mid = (left + right) / 2
print(int(mid))
print(sys.maxsize)
print(sys.maxsize + sys.maxsize)
print(sys.maxsize * 10000000000)
"""
4611686018427387904
9223372036854775807
18446744073709551614
92233720368547758070000000000
"""
-
边界问题
开区间用
(a, b)来表示，闭区间用[a, b]来表示。闭区间包括了两个端点a和b，而开区间不包含两个端点a和b。
通常是在给定的数组中查找目标值，如果查找范围不包括最后一个元素，即左闭右开区间。
# python [left...right] 查找范围是所有元素
def binarySearch(arr, target):
'''
定义：在[left...right]的范围里寻找target，因为这里定义是需要将right归入范围区间，end inclusive，所以while循环的边界需要包含right
'''
# len(arr) - 1
left, right = 0, len(arr) - 1
# <=
while left <= right:
# python3不影响，为保持统一最好还是left + (right - left) // 2
mid = (left + right) // 2
if arr[mid] == target:
return mid
if target > arr[mid]:
# [mid + 1, right]
left = mid + 1
elif target < arr[mid]:
# [left, mid - 1]
right = mid - 1
return -1
左闭右开，不包括end区间，end exclusive
# python [left...right) 查找范围不包括数组中最后的元素
def binarySearch(arr, target):
'''
定义：在[left...right)的范围里寻找target，因为这里定义是不需要将end归入范围区间；
exclusive，所以while循环的边界小于end即可，因为length本身长度会比index大1，
相对应的，每次target的value小于arr[mid]的时候，重新定义新的end，
也选择exclusive的模式，r=mid即可
'''
# len(arr)
left, right = 0, len(arr)
# <
while left < right:
mid = left + (right - left) // 2
if arr[mid] == target:
return mid
if target > arr[mid]:
left = mid + 1
elif target < arr[mid]:
right = mid
return -1
-
注意left和right赋值错误容易导致死循环
-
如果数组中有重复多个目标值，返回目标值的位置（索引），一般是靠近中心的位置，如果想要返回最左侧或最右侧的索引怎么办（在一个数组中有多个相同的值） 比如：
# 返回索引4 现在想要返回第一次出现目标值的索引3，或者最后出现目标值的索引5
print(binarySearch([1, 8, 9, 88, 88, 88, 99, 333, 999], 88))
寻找左侧边界的二分查找
当每次找到目标值时，都把mid赋值给right，把区间缩至[left, 新的right]，不断逼近最左侧的目标值
# 函数的返回值（即left变量的值）取值区间是闭区间[0, len(arr)]
def left_bound(arr, target):
if arr is None or len(arr) == 0:
return -1
left, right = 0, len(arr)
# <
while left < right:
mid = left + (right - left) // 2
if arr[mid] == target:
# right
right = mid
if target > arr[mid]:
left = mid + 1
elif target < arr[mid]:
right = mid
if left == len(arr):
# 目标值比数组中任意元素都大
return -1
return left if arr[left] == target else -1
# 保持和常规二分查找左右全闭区间一致的写法
def left_bound2(arr, target):
if arr is None or len(arr) == 0:
return -1
left, right = 0, len(arr) - 1
# <=
while left <= right:
mid = left + (right - left) // 2
if arr[mid] == target:
# right
right = mid - 1
if target > arr[mid]:
left = mid + 1
elif target < arr[mid]:
right = mid - 1
if left == len(arr) or arr[left] != target:
return -1
return left
寻找右侧边界的二分查找
当每次找到目标值时，都把mid赋值给left，把区间缩至[新的left, right]，不断逼近最右侧的目标值
# 保持和常规二分查找左右全闭区间一致的写法
def right_bound2(arr, target):
if arr is None or len(arr) == 0:
return -1
left, right = 0, len(arr) - 1
# <=
while left <= right:
mid = left + (right - left) // 2
if arr[mid] == target:
# left
left = mid + 1
if target > arr[mid]:
left = mid + 1
elif target < arr[mid]:
right = mid - 1
if right == len(arr) or arr[right] != target:
return -1
return right
-
如果循环查找过程中，边界的数在运行中出现更改，如何避免出现数组越界而报错
# 去掉mid + 1 和 - 1 加上两个if判断
def binary_search_another(arr, target):
left, right = 0, len(arr) - 1
while left + 1 < right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif target > arr[mid]:
left = mid
elif target < arr[mid]:
right = mid
if arr[left] == target:
return left
if arr[right] == target:
return right
return -1
JDK中的二分查找算法实现
JDK8中java.util.Collections.java里的binarySearch方法
// List有可能是随机访问的ArrayList（实现了RandomAccess），也可能是LinkedList
public static <T>
int binarySearch(List<? extends Comparable<? super T>> list, T key) {
// BINARYSEARCH_THRESHOLD为5000
if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD)
return Collections.indexedBinarySearch(list, key);
else
return Collections.iteratorBinarySearch(list, key);
}
// indexedBinarySearch，注意mid的实现
private static <T>
int indexedBinarySearch(List<? extends Comparable<? super T>> list, T key) {
int low = 0;
int high = list.size()-1;
while (low <= high) {
// >>> 无符号右移，忽略符号位，空位都以0补齐
int mid = (low + high) >>> 1;
// 根据下标index获取元素值
Comparable<? super T> midVal = list.get(mid);
int cmp = midVal.compareTo(key);
if (cmp < 0)
low = mid + 1;
else if (cmp > 0)
high = mid - 1;
else
return mid; // key found
}
return -(low + 1); // key not found
}
// iteratorBinarySearch
private static <T>
int iteratorBinarySearch(List<? extends Comparable<? super T>> list, T key)
{
int low = 0;
int high = list.size()-1;
ListIterator<? extends Comparable<? super T>> i = list.listIterator();
while (low <= high) {
int mid = (low + high) >>> 1;
// 从迭代器中获取元素值
Comparable<? super T> midVal = get(i, mid);
int cmp = midVal.compareTo(key);
if (cmp < 0)
low = mid + 1;
else if (cmp > 0)
high = mid - 1;
else
return mid; // key found
}
return -(low + 1); // key not found
}
猜你喜欢
点一下，代码无 Bug