二元搜索(Binary Search)算法又称为二分搜索(Half-Interval Search)算法或是对数搜索(Logarithmic Search)算法,顾名思义,这套算法的核心思想就在于「二分」,可以在已排序好的串行中进行高效率的搜索。
在一个已排序好的串行中搜索元素是一件轻松容易的事情,我们可以先设置搜索范围,每次都用这范围最中间的元素来与要查找的目标元素比大小,如果要查找的目标元素比较大,表示如果目标元素存在于该串行中的话,其一定是位在目前范围的后半段(值大的那段);反之,如果要查找的目标元素比较小,表示如果目标元素存在于该串行中的话,其一定是位在目前范围的前半段(值小的那段)。在下次搜索的时候,也是一样拿目标元素与前半段或是后半段的正中央元素进行比较,如此反复动作,直到找出相同的元素为止;或者直到查找范围内已经没有任何元素时,表示要找的元素并不存在于串行中。
/// 二元搜索法,使用递归。此为用来递归调用的函数。
pub fn binary_search_recursively(array: &[i32], target_element: i32, start: usize, end: usize) -> Option<usize> {
if end < start {
None
} else {
let middle = start + ((end - start) >> 1);
match target_element.cmp(&array[middle]) {
Ordering::Equal => Some(middle),
Ordering::Greater => binary_search_recursively(array, target_element, middle + 1, end),
Ordering::Less => {
if middle > 0 {
binary_search_recursively(array, target_element, start, middle - 1)
} else {
None
}
}
}
}
}
/// 二元搜索法,使用递归。
pub fn binary_search(array: &[i32], target_element: i32) -> Option<usize> {
if array.is_empty() {
return None;
}
binary_search_recursively(array, target_element, 0, array.len() - 1)
}
>> 1 等同于「除以 2 取整数」,先减后加是为了避免直接计算 end + start 可能会溢出(超过无号整数的表示范围,而使得程序 panic)。
/**
* 二元搜索法,使用递归。此为用来递归调用的函数。
*/
public static int binarySearchRecursively(final int[] array, final int targetElement, final int start, final int end) {
if (end < start) {
return -1;
}
final int middle = (end + start) >>> 1;
if (array[middle] == targetElement) {
return middle;
} else if (targetElement > array[middle]) {
return binarySearchRecursively(array, targetElement, middle + 1, end);
} else {
return binarySearchRecursively(array, targetElement, start, middle - 1);
}
}
/**
* 二元搜索法,使用递归。
*/
public static int binarySearch(final int[] array, final int targetElement) {
return binarySearchRecursively(array, targetElement, 0, array.length - 1);
}
>>> 1 等同于「除以 2 取整数」,利用无号右位移(unsigned right shift)还可以避免 end + start 溢出时导致结果错误(超过有号正整数的表示范围,而变成负数)。
/**
* 二元搜索法,使用递归。此为用来递归调用的函数。
*/
function binarySearchRecursively(array: number[], targetElement: number, start: number, end: number) {
if (end < start) {
return -1;
}
const middle = start + ((end - start) >> 1);
if (array[middle] === targetElement) {
return middle;
} else if (targetElement > array[middle]) {
return binarySearchRecursively(array, targetElement, middle + 1, end);
} else {
return binarySearchRecursively(array, targetElement, start, middle - 1);
}
}
/**
* 二元搜索法,使用递归。
*/
function binarySearch(array: number[], targetElement: number) {
return binarySearchRecursively(array, targetElement, 0, array.length - 1);
}
>> 1 等同于「除以 2 取整数」,先减后加是为了避免直接计算
end + start 可能会超过
232 - 1,若是超过,JavaScript 内置的 32-bit 整数字移功能也就无效了。不过这边其实也可以写成
(end + start) >>> 1,
>>> 1 也是等同于「除以 2 取整数」,但利用无号右位移(unsigned right shift)还可以避免
end + start 超过
231 - 1 时进行有号位移(signed shift)后会变成负数的问题。在数组长度不超过
231 的情况下,以上两种写法都能算出正确的结果。不过 JavaScript 的数组最大长度是
232 - 1,如果数组长度超过
231,
end - start 有可能会超过
231 - 1,
end + start 也有可能会超过
232 - 1,此时要写成
start + ((end - start) >>> 1) 才不会算错。
// 二元搜索法,使用递归。此为用来递归调用的函数。
func BinarySearchRecursively(array []int, targetElement int, start int, end int) int {
if end < start {
return -1
}
middle := int(uint(end+start) >> 1)
if array[middle] == targetElement {
return middle
} else if targetElement > array[middle] {
return BinarySearchRecursively(array, targetElement, middle+1, end)
} else {
return BinarySearchRecursively(array, targetElement, start, middle-1)
}
}
// 二元搜索法,使用递归。
func BinarySearch(array []int, targetElement int) (index int) {
return BinarySearchRecursively(array, targetElement, 0, len(array)-1)
}
>> 1 等同于「除以 2 取整数」,把
end+start 的结果先转成无号整数(unsigned integer)是因为它可能会溢出(超过有号正整数的表示范围,而变成负数)。
在实作程序的时候,应该要避免使用递归(Recursive)的结构,因为递归需要不断地重新建构函数的堆栈空间,硬件资源的负担会比较大,且若是递归层数过多还会导致堆栈溢出(Stack Overflow)。所以比较好的做法还是在一个函数内以循环迭代的方式来完成。
/// 二元搜索法,使用循环来迭代。
pub fn binary_search(array: &[i32], target_element: i32) -> Option<usize> {
if array.is_empty() {
return None;
}
let mut start = 0;
let mut end = array.len() - 1;
while end >= start {
let middle = start + ((end - start) >> 1);
match target_element.cmp(&array[middle]) {
Ordering::Equal => {
return Some(middle);
}
Ordering::Greater => {
start = middle + 1;
}
Ordering::Less => {
if middle > 0 {
end = middle - 1;
} else {
break;
}
}
}
}
None
}
或
/// 二元搜索法,使用标准函数库(迭代)。
pub fn binary_search(array: &[i32], target_element: i32) -> Option<usize> {
array.binary_search(&target_element).ok()
}
/**
* 二元搜索法,使用循环来迭代。
*/
public static int binarySearch(final int[] array, final int targetElement) {
int start = 0;
int end = array.length - 1;
while (end >= start) {
final int middle = (end + start) >>> 1;
if (targetElement == array[middle] ) {
return middle;
} else if (targetElement > array[middle]) {
start = middle + 1;
} else {
end = middle - 1;
}
}
return -1;
}
或
/**
* 二元搜索法,使用标准函数库(迭代)。
*/
public static int binarySearch(final int[] array, final int targetElement) {
final int index = Arrays.binarySearch(array, targetElement);
if (index < 0) {
return -1;
}
return index;
}
/**
* 二元搜索法,使用循环来迭代。
*/
function binarySearch(array: number[], targetElement: number) {
let start = 0;
let end = array.length - 1;
while (end >= start) {
const middle = start + ((end - start) >> 1);
if (targetElement === array[middle]) {
return middle;
} else if (targetElement > array[middle]) {
start = middle + 1;
} else {
end = middle - 1;
}
}
return -1;
}
// 二元搜索法,使用循环来迭代。
func BinarySearch(array []int, targetElement int) int {
start := 0
end := len(array) - 1
for end >= start {
middle := int(uint(end+start) >> 1)
if targetElement == array[middle] {
return middle
} else if targetElement > array[middle] {
start = middle + 1
} else {
end = middle - 1
}
}
return -1
}
或
// 二元搜索法,使用标准函数库(迭代)。
func BinarySearch(array []int, targetElement int) int {
length := len(array)
index := sort.Search(length, func(i int) bool {
return array[i] >= targetElement
})
if index < length && array[index] == targetElement {
return index
} else {
return -1
}
}