7大主流语言二分搜索算法的不同实现对比
大家好，我是 V 哥。二分搜索算法因为每次操作都会将搜索范围减半，使其在处理大型已排序数组时非常高效。通过不断比较中间元素和目标元素，逐步缩小搜索范围，最终找到目标元素或确定其不存在。该算法的时间复杂度为 O ( l o g n ) O(log n) O(logn)。这篇文章 V 哥罗列了7大常用语言二分搜索算法（或者叫二分查找算法）的实现，我们来一起比较一下各自的特点。
JavaScript语言实现二分搜索
function binarySearch(arr, target) {
let left = 0;
let right = arr.length - 1;
while (left <= right) {
// 计算中间元素的索引
let mid = Math.floor((left + right) / 2);
if (arr[mid] === target) {
return mid;
} else if (arr[mid] < target) {
// 如果中间元素小于目标元素，更新左边界
left = mid + 1;
} else {
// 如果中间元素大于目标元素，更新右边界
right = mid - 1;
}
}
return -1;
}
// 示例调用
let arr = [1, 3, 5, 7, 9, 11, 13, 15];
let target = 7;
console.log(binarySearch(arr, target));
代码解释：
- 首先，我们定义了一个名为
binarySearch的函数，它接收一个已排序的数组arr和一个目标元素target作为参数。- 我们使用
left和right变量来表示搜索范围的左右边界，初始时，left为 0，right为数组长度减 1。 - 在
while循环中，只要left小于等于right，我们就会继续搜索。 - 计算中间元素的索引
mid，使用Math.floor((left + right) / 2)确保结果为整数。 - 如果中间元素等于目标元素，返回中间元素的索引。
- 如果中间元素小于目标元素，将
left更新为mid + 1，因为目标元素在右半部分。 - 如果中间元素大于目标元素，将
right更新为mid - 1，因为目标元素在左半部分。
- 我们使用
- 最后，如果未找到目标元素，返回 -1。
使用方法：
- 调用
binarySearch函数，传入一个已排序的数组和要查找的目标元素。 - 例如：
let arr = [1, 3, 5, 7, 9, 11, 13, 15]; let target = 7; console.log(binarySearch(arr, target));会在数组中查找 7，并输出其索引（如果存在）或 -1（如果不存在）。
Java语言实现二分搜索
public class BinarySearch {
public static int binarySearch(int[] arr, int target) {
int left = 0;
int right = arr.length - 1;
while (left <= right) {
// 计算中间元素的索引
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
// 如果中间元素小于目标元素，更新左边界
left = mid + 1;
} else {
// 如果中间元素大于目标元素，更新右边界
right = mid - 1;
}
}
return -1;
}
public static void main(String[] args) {
int[] arr = {1, 3, 5, 7, 9, 11, 13, 15};
int target = 7;
System.out.println(binarySearch(arr, target));
}
}
代码解释：
- 首先，定义了一个名为
BinarySearch的类，其中包含一个静态方法binarySearch和main方法。- 在
binarySearch方法中，接收一个整数数组arr和一个目标整数target作为参数。 left和right变量分别表示搜索范围的左右边界，初始时left为 0，right为数组长度减 1。- 进入
while循环，只要left小于等于right，循环继续。 - 计算中间元素的索引
mid，使用left + (right - left) / 2可以避免整数溢出问题。 - 若
arr[mid]等于target，返回mid作为目标元素的索引。 - 若
arr[mid]小于target，将left更新为mid + 1，表示目标元素在右半部分。 - 若
arr[mid]大于target，将right更新为mid - 1，表示目标元素在左半部分。 - 若未找到目标元素，最终返回 -1。
- 在
- 在
main方法中，创建一个测试数组和目标元素，调用binarySearch方法并打印结果。
使用方法：
- 可直接运行
BinarySearch类，在main方法中可以修改测试数组arr和目标元素target的值，然后程序会调用binarySearch方法进行二分搜索并输出结果。
C语言实现二分搜索
#include <stdio.h>
// 二分搜索函数
int binarySearch(int arr[], int n, int target) {
int left = 0;
int right = n - 1;
while (left <= right) {
// 计算中间元素的索引
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
// 如果中间元素小于目标元素，更新左边界
left = mid + 1;
} else {
// 如果中间元素大于目标元素，更新右边界
right = mid - 1;
}
}
return -1;
}
// 测试函数
int main() {
int arr[] = {1, 3, 5, 7, 9, 11, 13, 15};
int n = sizeof(arr) / sizeof(arr[0]);
int target = 7;
int result = binarySearch(arr, n, target);
if (result == -1) {
printf("元素未找到\n");
} else {
printf("元素在数组中的索引为：%d\n", result);
}
return 0;
}
代码解释：
- 代码整体实现了二分搜索算法，该算法要求输入的数组是已排序的。
binarySearch函数：- 接收三个参数，
arr是要搜索的整数数组，n是数组元素的数量，target是要查找的目标元素。 left和right分别代表搜索范围的左右边界，初始化为 0 和n - 1。- 在
while循环中，计算中间元素的索引mid，使用left + (right - left) / 2避免溢出。 - 若
arr[mid]等于target，返回mid作为结果。 - 若
arr[mid]小于target，将left更新为mid + 1，意味着目标元素在右半部分。 - 若
arr[mid]大于target，将right更新为mid - 1，意味着目标元素在左半部分。 - 若最终未找到，返回 -1。
- 接收三个参数，
main函数：- 定义一个测试数组
arr并初始化。 - 通过
sizeof(arr) / sizeof(arr[0])计算数组元素的数量n。 - 设定要查找的目标元素
target。 - 调用
binarySearch函数进行查找，并将结果存储在result中。 - 根据结果输出相应信息。
- 定义一个测试数组
使用方法：
- 可以修改
arr数组中的元素和target的值，以满足不同的搜索需求。 - 编译并运行程序，程序会调用
binarySearch函数查找target，并输出结果。
GO语言实现二分搜索
package main
import "fmt"
// binarySearch 二分搜索函数
func binarySearch(arr []int, target int) int {
left := 0
right := len(arr) - 1
for left <= right {
// 计算中间元素的索引
mid := left + (right-left)/2
if arr[mid] == target {
return mid
} else if arr[mid] < target {
// 如果中间元素小于目标元素，更新左边界
left = mid + 1
} else {
// 如果中间元素大于目标元素，更新右边界
right = mid - 1
}
}
return -1
}
func main() {
arr := []int{1, 3, 5, 7, 9, 11, 13, 15}
target := 7
result := binarySearch(arr, target)
if result == -1 {
fmt.Println("元素未找到")
} else {
fmt.Printf("元素在数组中的索引为：%d\n", result)
}
}
代码解释：
- 此 Go 语言代码实现了二分搜索算法。
binarySearch函数：- 接收一个整数切片
arr和一个整数target作为参数。 left和right变量表示搜索范围的左右边界，初始时，left为 0，right为切片长度减 1。- 循环使用
for语句，只要left小于等于right就会持续进行。 - 计算中间元素的索引
mid，通过left + (right-left)/2避免整数溢出。 - 若
arr[mid]等于target，返回mid作为结果。 - 若
arr[mid]小于target，将left更新为mid + 1，表示目标元素在右半部分。 - 若
arr[mid]大于target，将right更新为mid - 1，表示目标元素在左半部分。 - 若最终未找到目标元素，返回 -1。
- 接收一个整数切片
main函数：- 定义一个测试切片
arr并初始化。 - 定义要查找的目标元素
target。 - 调用
binarySearch函数进行查找，并将结果存储在result中。 - 根据结果输出相应信息。
- 定义一个测试切片
使用方法：
- 可修改
arr切片中的元素和target的值，以适应不同的查找需求。 - 运行代码，程序会调用
binarySearch函数查找target并输出相应结果。
Python语言实现二分搜索
def binary_search(arr, target):
left = 0
right = len(arr) - 1
while left <= right:
# 计算中间元素的索引
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
# 如果中间元素小于目标元素，更新左边界
left = mid + 1
else:
# 如果中间元素大于目标元素，更新右边界
right = mid - 1
return -1
# 测试代码
if __name__ == "__main__":
arr = [1, 3, 5, 7, 9, 11, 13, 15]
target = 7
result = binary_search(arr, target)
if result == -1:
print("元素未找到")
else:
print(f"元素在数组中的索引为: {result}")
代码解释：
- 此 Python 代码实现了二分搜索算法。
binary_search函数：- 接收一个列表
arr和一个元素target作为参数。 left和right变量分别表示搜索范围的左右边界，初始时left为 0，right为列表长度减 1。- 循环使用
while语句，只要left小于等于right就会继续执行。 - 计算中间元素的索引
mid，使用(left + right) // 2确保结果为整数。 - 若
arr[mid]等于target，返回mid作为结果。 - 若
arr[mid]小于target，将left更新为mid + 1，意味着目标元素在右半部分。 - 若
arr[mid]大于target，将right更新为mid - 1，意味着目标元素在左半部分。 - 若最终未找到目标元素，返回 -1。
- 接收一个列表
- 测试部分：
- 定义一个测试列表
arr并初始化。 - 定义要查找的目标元素
target。 - 调用
binary_search函数进行查找，并将结果存储在result中。 - 根据结果输出相应信息。
- 定义一个测试列表
使用方法：
- 可以修改
arr列表中的元素和target的值，以满足不同的查找需求。 - 运行代码，程序会调用
binary_search函数查找target并输出结果。
Rust语言实现二分搜索
fn binary_search(arr: &[i32], target: i32) -> Option<usize> {
let mut left = 0;
let mut right = arr.len();
while left < right {
// 计算中间元素的索引
let mid = left + (right - left) / 2;
if arr[mid] == target {
return Some(mid);
} else if arr[mid] < target {
// 如果中间元素小于目标元素，更新左边界
left = mid + 1;
} else {
// 如果中间元素大于目标元素，更新右边界
right = mid;
}
}
None
}
fn main() {
let arr = [1, 3, 5, 7, 9, 11, 13, 15];
let target = 7;
match binary_search(&arr, target) {
Some(index) => println!("元素在数组中的索引为: {}", index),
None => println!("元素未找到"),
}
}
代码解释：
- 该 Rust 代码实现了二分搜索算法。
binary_search函数：- 接收一个
i32类型的切片arr和一个i32类型的目标元素target作为参数。 left和right变量分别表示搜索范围的左右边界，初始时left为 0，right为切片长度。- 在
while循环中，只要left小于right，就会继续搜索。 - 计算中间元素的索引
mid，使用left + (right - left) / 2。 - 若
arr[mid]等于target，返回Some(mid)作为结果。 - 若
arr[mid]小于target，将left更新为mid + 1，表示目标元素在右半部分。 - 若
arr[mid]大于target，将right更新为mid，表示目标元素在左半部分。 - 若最终未找到目标元素，返回
None。
- 接收一个
main函数：- 定义一个测试数组
arr并初始化。 - 定义要查找的目标元素
target。 - 调用
binary_search函数进行查找，并使用match表达式根据结果进行不同的输出。
- 定义一个测试数组
使用方法：
- 可以修改
arr数组中的元素和target的值，以满足不同的查找需求。 - 编译并运行代码，程序会调用
binary_search函数查找target，并根据结果输出相应信息。
在 Rust 中，使用 Option 类型来表示可能存在或不存在的结果，Some 表示存在，None 表示不存在，这是一种更安全的处理可能缺失值的方式。
C#语言实现二分搜索
using System;
class BinarySearch {
// 二分搜索函数
public static int BinarySearchFunc(int[] arr, int target) {
int left = 0;
int right = arr.Length - 1;
while (left <= right) {
// 计算中间元素的索引
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
// 如果中间元素小于目标元素，更新左边界
left = mid + 1;
} else {
// 如果中间元素大于目标元素，更新右边界
right = mid - 1;
}
}
return -1;
}
static void Main() {
int[] arr = { 1, 3, 5, 7, 9, 11, 13, 15 };
int target = 7;
int result = BinarySearchFunc(arr, target);
if (result == -1) {
Console.WriteLine("元素未找到");
} else {
Console.WriteLine("元素在数组中的索引为：" + result);
}
}
}
代码解释：
- 该 C# 代码实现了二分搜索算法。
BinarySearchFunc函数：- 接收一个整数数组
arr和一个整数目标元素target作为参数。 left和right分别表示搜索范围的左右边界，初始时left为 0，right为数组长度减 1。- 进入
while循环，只要left小于等于right，循环继续。 - 计算中间元素的索引
mid，使用left + (right - left) / 2计算。 - 若
arr[mid]等于target，返回mid作为结果。 - 若
arr[mid]小于target，将left更新为mid + 1，表示目标元素在右半部分。 - 若
arr[mid]大于target，将right更新为mid - 1，表示目标元素在左半部分。 - 若最终未找到目标元素，返回 -1。
- 接收一个整数数组
Main函数：- 定义一个测试数组
arr并初始化。 - 定义一个目标元素
target。 - 调用
BinarySearchFunc函数进行查找，并将结果存储在result中。 - 根据结果输出相应信息。
- 定义一个测试数组
使用方法：
- 可以修改
arr数组中的元素和target的值，以满足不同的查找需求。 - 运行程序，将调用
BinarySearchFunc函数查找target并输出结果。
小结一下
以上七种语言实现二分搜索算法，我们来一起对比一下：
一、实现思路的共性：
- 基本逻辑：
- 所有语言实现的二分搜索算法都遵循相同的基本逻辑。首先确定搜索范围，用左右边界
left和right来表示。 - 在循环中，通过计算中间元素的索引
mid来将搜索范围一分为二。计算mid的方式一般是(left + right) / 2或其变体，部分语言为避免溢出使用left + (right - left) / 2。 - 比较中间元素
arr[mid]与目标元素target的大小关系：- 若相等，返回
mid作为目标元素的索引。 - 若
arr[mid]小于target，更新左边界left = mid + 1，将搜索范围缩小到右半部分。 - 若
arr[mid]大于target，更新右边界right = mid - 1，将搜索范围缩小到左半部分。
- 若相等，返回
- 循环继续，直到找到目标元素或
left大于right，表示元素不存在，此时返回 -1 或相应的表示未找到的标志（如None在 Rust 中）。
- 所有语言实现的二分搜索算法都遵循相同的基本逻辑。首先确定搜索范围，用左右边界
二、语言特性的差异：
-
变量声明和类型：
- C 语言：使用
int等基本数据类型声明变量，如int left = 0;，数组作为参数传递时需额外传递数组长度。 - Java：使用
int等基本数据类型，需要将二分搜索方法封装在类中，方法可声明为静态。 - JavaScript：变量声明使用
let或var，是动态类型语言，参数和变量类型通常无需显式声明。 - Go：变量声明使用
:=进行简洁声明，类型推断较为方便。 - Python：使用动态类型，无需显式声明变量类型，代码简洁。
- Rust：具有严格的类型系统，使用
let声明变量，并且对变量的可变性有严格控制（let mut表示可变变量），使用Option<usize>来表示可能存在或不存在的结果，增强了代码的安全性。 - csharp：使用
int等基本数据类型，变量声明通常使用int left = 0;等形式，将方法封装在类中。
- C 语言：使用
-
循环结构：
- C 语言：使用
while循环，如while (left <= right) {...}。 - Java：使用
while循环，与 C 语言类似。 - JavaScript：使用
while循环，也可以使用for循环实现类似逻辑。 - Go：使用
for循环，简洁地实现了while循环的功能，如for left <= right {...}。 - Python：使用
while循环，例如while left <= right:。 - ArkTS：使用
while循环，与 JavaScript 类似。 - Rust：使用
while循环，如while left < right {...}，注意其边界条件与部分语言略有不同。 - csharp ： 使用
while循环，与 C 语言和 Java 类似。
- C 语言：使用
-
数组或切片操作：
- C 语言：使用
arr[mid]来访问数组元素，数组作为指针和长度传递。 - Java：使用
arr[mid]来访问数组元素，数组是对象。 - JavaScript：使用
arr[mid]访问数组元素，数组是动态对象。 - Go：使用
arr[mid]访问切片元素，切片是引用类型。 - Python：使用
arr[mid]访问列表元素，列表是动态数据结构。 - Rust：使用
arr[mid]访问切片元素，切片是安全的，且编译器会进行越界检查。 - csharp：使用
arr[mid]访问数组元素，数组是引用类型。
- C 语言：使用
-
函数和方法的定义：
- C 语言：使用函数，如
int binarySearch(int arr[], int n, int target) {...}。 - Java：使用类中的静态方法，如
public static int binarySearch(int[] arr, int target) {...}。 - JavaScript：使用函数，如
function binarySearch(arr, target) {...}。 - Go：使用函数，如
func binarySearch(arr []int, target int) int {...}。 - Python：使用函数，如
def binarySearch(arr, target):...。 - Rust：使用函数，如
fn binarySearch(arr: &[i32], target: i32) -> Option<usize> {...}，使用了函数式编程风格，通过Option处理可能的结果。 - csharp：使用类中的静态方法，如
public static int BinarySearchFunc(int[] arr, int target) {...}。
- C 语言：使用函数，如
-
处理结果表示：
- 除了Rust语言使用
None表示未找到元素，使用Some(index)表示找到元素，利用Option类型处理可能不存在的结果，避免空指针等错误外，其它6种语言都是使用-1表示未找到元素。
- 除了Rust语言使用
三、性能考虑：
- 时间复杂度：
- 所有语言实现的二分搜索算法的时间复杂度均为 O ( l o g n ) O(log n) O(logn)，因为每次操作都会将搜索范围减半，对于较大的已排序数组或切片，该算法具有较高的搜索效率。
- 空间复杂度：
- 空间复杂度通常为
O
(
1
)
O(1)
O(1)，因为只使用了几个额外的变量（如
left、right和mid）来维护搜索范围，不随输入规模的增大而显著增加。
- 空间复杂度通常为
O
(
1
)
O(1)
O(1)，因为只使用了几个额外的变量（如
总体而言，不同语言在实现二分搜索算法时虽然在语法和语言特性上有所不同，但基本思路一致。选择哪种语言取决于项目需求、开发团队的技能、平台兼容性等因素。在实现细节上，如变量声明、类型系统、错误处理和语言的特定特性等方面存在差异，但这些差异主要影响代码的书写和维护方式，而不影响算法的核心逻辑和性能。兄弟们觉得哪种语言的实现最简单呢？欢迎评论区下方发表你的见解和赐教。今天的内容就到这里，感谢关注威哥爱编程，全栈开发就你行。