导入
在有序数组上实现二分查找
给定一个已排序的整数数组，返回指定值的索引。
陈述
二分查找 是一种高效的算法，用于在已排序的数组中查找目标值的位置。它通过反复将数组一分为二，将中间元素与目标值进行比较。根据比较结果，算法会将搜索范围缩小到数组的左半部分或右半部分，直到找到目标值或子数组大小变为零。
给定一个按升序排列的整数数组 nums 和一个整数值 target。如果 target 存在于数组中，则返回其索引；否则返回 -1。
示例
给定以下已排序的数组，若目标值为 9，则二分查找返回 2。
...
示例输入
1nums = [1, 3, 9, 10, 12] 2target = 9
期望输出
12
自行尝试
多标签代码
C++
1#include <iostream> 2 3using namespace std; 4 5int BinarySearch(int nums[], int target, int length) { 6 //TODO: 写你的代码 7 return -1; 8}
Java
1class BinarySearch { 2 static int binarySearch(int[] nums, int target) { 3 // TODO: 写你的代码 4 return -1; 5 } 6}
Python
1def binary_search(nums, target): 2 #TODO: 写你的代码 3 return -1
JS
1let binarySearch = function(nums, target) { 2 //TODO: 写你的代码 3 return -1; 4};
Ruby
1def binary_search(nums, target) 2#TODO: 写你的代码 3 return -1 4end
Go
1package main 2import ( 3 "fmt" 4 "strconv" 5 "encoding/json" 6 "strings" 7) 8 9func BinarySearch(nums []int, target int) int { 10 // TODO: 写你的代码 11 return -1 12}
解法 1：迭代
在迭代方法中，算法的工作方式如下：
- 每一步都考虑从
low到high索引之间的数组。 - 计算
mid索引。 - 如果
mid索引处的元素等于目标值，则返回mid。 - 如果
mid处的元素大于目标值：- 将
high索引改为mid - 1。 low的值保持不变。
- 将
- 如果
mid处的元素小于目标值：- 将
low改为mid + 1。 high的值保持不变。
- 将
- 当
low的值大于high的值时，表示目标值不存在。因此返回-1。
多标签代码
C++
1#include <iostream> 2#include <vector> 3 4using namespace std; 5 6int BinarySearch(int nums[], int target, int length) { 7 int low = 0; 8 int high = length - 1; 9 10 while (low <= high) { 11 12 // 使用向下取整计算中间位置 13 int mid = low + ((high - low) / 2); 14 15 // 目标值位于数组中间 16 if (nums[mid] == target) { 17 return mid; 18 } 19 20 // 目标值位于左子数组中 21 else if (target < nums[mid]) { 22 high = mid - 1; 23 } 24 25 // 目标值位于右子数组中 26 else if (target > nums[mid]) { 27 low = mid + 1; 28 } 29 } 30 31 // 目标值不在数组中 32 return -1; 33} 34 35int main() { 36 vector<vector<int> > nums = { 37 {}, {0, 1}, {1, 2, 3}, {-1, 0, 3, 5, 9, 12}, {-1, 0, 3, 5, 9, 12}}; 38 vector<int> sizes = {0, 2, 3, 6, 6}; 39 vector<int> targets = {12, 1, 3, 9, 2}; 40 for (int i = 0; i < nums.size(); i++) { 41 cout << i + 1 << ". 要搜索的数组: "; 42 // 自定义函数用于整洁打印列表 43 PrintList(nums[i]); 44 cout << " 目标值: " << targets[i] << endl; 45 int index = BinarySearch(nums[i].data(), targets[i], sizes[i]); 46 if (index != -1) { 47 cout << " " << targets[i] << " 在数组中存在，索引为 " << index << endl; 48 } else { 49 cout << " " << targets[i] << " 不在数组中，返回值为 " << index << endl; 50 } 51 cout << "------------------------------------------------------------------------------------------------------\n" << endl; 52 } 53}
Java
1// 导入所需函数 2import java.util.*; 3 4class BinarySearch { 5 static int binarySearch(int[] nums, int target) { 6 int low = 0; 7 int high = nums.length - 1; 8 9 while (low <= high) { 10 // 使用向下取整计算中间位置 11 int mid = low + ((high - low) / 2); 12 13 // 目标值位于数组中间 14 if (nums[mid] == target) { 15 return mid; 16 } 17 18 // 目标值位于左子数组中 19 else if (target < nums[mid]) { 20 high = mid - 1; 21 } 22 23 // 目标值位于右子数组中 24 else if (target > nums[mid]) { 25 low = mid + 1; 26 } 27 } 28 29 // 目标值不在数组中 30 return -1; 31 } 32 33 public static void main(String[] args) { 34 int[][] numsLists = {{}, {0, 1}, {1, 2, 3}, {-1, 0, 3, 5, 9, 12}, {-1, 0, 3, 5, 9, 12}}; 35 int[] targetList = {12, 1, 3, 9, 2}; 36 for (int i = 0; i < numsLists.length; i++) { 37 int[] nums = numsLists[i]; 38 int target = targetList[i]; 39 int index = binarySearch(nums, target); 40 System.out.println(i + 1 + ". 要搜索的数组: " + Arrays.toString(nums)); 41 System.out.println(" 目标值: " + targetList[i]); 42 if (index != -1) { 43 System.out.println(" " + target + " 在数组中存在，其索引为 " + index); 44 } else { 45 System.out.println(" " + target + " 不在数组中，返回值为 " + index); 46 } 47 System.out.println( 48 "----------------------------------------------------------------------------------------------------\n"); 49 } 50 } 51}
Python
1def binary_search(nums, target): 2 low = 0 3 high = len(nums) - 1 4 5 while low <= high: 6 # 使用向下取整计算中间位置 7 mid = low + ((high - low) // 2) 8 9 # 目标值位于数组中间 10 if nums[mid] == target: 11 return mid 12 13 # 目标值位于左子数组中 14 elif target < nums[mid]: 15 high = mid - 1 16 17 # 目标值位于右子数组中 18 elif target > nums[mid]: 19 low = mid + 1 20 21 # 目标值不在数组中 22 return -1 23 24def main(): 25 nums_lists = [[], [0,1], [1,2,3], [-1,0,3,5,9,12], [-1,0,3,5,9,12]] 26 target_list = [12, 1, 3, 9, 2] 27 for i in range(len(nums_lists)): 28 nums = nums_lists[i] 29 target = target_list[i] 30 index = binary_search(nums, target) 31 print(str(i+1) + ". 要搜索的数组: " + str(nums)) 32 print(" 目标值: " + str(target)) 33 if index != -1: 34 print(" " + str(target) + " 在数组中存在，索引为", index) 35 else: 36 print(" " + str(target) + " 不在数组中，返回值为", index) 37 print("----------------------------------------------------------------------------------------------------\n") 38 39if __name__ == '__main__': 40 main()
JS
1let binarySearch = function(nums, target) { 2 let low = 0; 3 let high = nums.length - 1; 4 5 while (low <= high) { 6 7 // 使用向下取整计算中间位置 8 let mid = low + Math.floor((high - low) / 2); 9 10 // 目标值位于数组中间 11 if (nums[mid] === target) { 12 return mid; 13 } 14 15 // 目标值位于左子数组中 16 if (target < nums[mid]) { 17 high = mid - 1; 18 } 19 // 目标值位于右子数组中 20 else { 21 low = mid + 1; 22 } 23 } 24 // 目标值不在数组中 25 return -1; 26}; 27 28let numsLists = [[], [0,1], [1,2,3], [-1,0,3,5,9,12], [-1,0,3,5,9,12]]; 29let targetList = [12, 1, 3, 9, 2]; 30for(let i=0; i<numsLists.length; i++){ 31 let nums = numsLists[i]; 32 let target = targetList[i]; 33 let index = binarySearch(nums, target); 34 // 使用自定义函数打印格式化数组 35 console.log(i+1 + ". 要搜索的数组: " + printArray(nums)); 36 console.log(" 目标值: " + String(target)); 37 if(index!= -1) 38 console.log(" " + String(target) + " 在数组中存在，索引为", index); 39 else 40 console.log(" " + String(target) + " 不在数组中，返回值为", index); 41 console.log("----------------------------------------------------------------------------------------------------\n"); 42 43}
Ruby
1def binary_search(nums, target) 2 low, high = 0, nums.length() - 1 3 4 while low <= high 5 # 计算中间位置 6 mid = low + ((high - low)/ 2).floor 7 8 # 目标值位于数组中间 9 if nums[mid] == target 10 return mid 11 12 # 目标值位于左子数组中 13 elsif target < nums[mid] 14 high = mid - 1 15 16 # 目标值位于右子数组中 17 elsif target > nums[mid] 18 low = mid + 1 19 end 20 end 21 # 目标值不在数组中 22 return -1 23end 24 25nums_lists = [[], [0,1], [1,2,3], [-1,0,3,5,9,12], [-1,0,3,5,9,12]] 26target_list = [12, 1, 3, 9, 2] 27nums_lists.length.times do |i| 28 nums = nums_lists[i] 29 target = target_list[i] 30 index = binary_search(nums, target) 31 if index != -1 32 print target.to_s + " 在数组中存在，其索引为 ", index.to_s 33 else 34 print target.to_s, " 不在数组中，返回值为 ", index.to_s 35 end 36 print "\n----------------------------------------------------------------------------------------------------\n" 37end
Go
1package main 2 3import ( 4 "fmt" 5 "strconv" 6) 7 8func BinarySearch(nums []int, target int) int { 9 low := 0 10 high := len(nums) - 1 11 for low <= high { 12 13 // 使用向下取整计算中间位置 14 mid := low + (high-low)/2 15 16 if nums[mid] == target { 17 // 目标值位于数组中间 18 return mid 19 } else if target < nums[mid] { 20 // 目标值位于左子数组中 21 high = mid - 1 22 } else { 23 // 目标值位于右子数组中 24 low = mid + 1 25 } 26 } 27 // 目标值不在数组中 28 return -1 29} 30 31/* ArrayToString 用于将整数数组转换为字符串。 32该函数作为辅助函数，在主函数中用于打印目的。 */ 33func ArrayToString(nums []int) string{ 34 if len(nums) == 0 { 35 return "[]" 36 } 37 res := "[" 38 for _, num := range nums { 39 res += strconv.Itoa(num) + ", " 40 } 41 res += "]" 42 return res[:len(res) - 3] + "]" 43} 44 45func main() { 46 numsLists := [][]int{ 47 {}, 48 {0, 1}, 49 {1, 2, 3}, 50 {-1, 0, 3, 5, 9, 12}, 51 {-1, 0, 3, 5, 9, 12}, 52 } 53 54 targetList := []int{12, 1, 3, 9, 2} 55 for i, nums := range numsLists { 56 target := targetList[i] 57 index := BinarySearch(nums, target) 58 fmt.Printf("%d. 要搜索的数组: %s\n", i+1, ArrayToString(nums)) 59 fmt.Printf(" 目标值: %d\n", target) 60 if index != -1 { 61 fmt.Printf(" %d 在数组中存在，索引为 %d\n", target, index) 62 } else { 63 fmt.Printf(" %d 不在数组中，返回值为 %d\n", target, index) 64 } 65 fmt.Printf( 66 "----------------------------------------------------------------------------------------------------\n\n", 67 ) 68 } 69}
时间复杂度
此解法的时间复杂度为对数级，。
空间复杂度
此解法的空间复杂度为常数级，。
解法 2：递归
在此解法中，我们将使用递归实现二分查找算法。每一步中，搜索函数会调用自身，使用已排序数组的左半部分或右半部分。
让我们看另一个示例：
多标签代码
C++
1#include <iostream> 2 3using namespace std; 4 5int BinarySearchRec(int nums[], int key, int low, int high) { 6 if (low > high) { 7 return -1; 8 } 9 10 // 使用向下取整计算中间位置 11 int mid = low + ((high - low) / 2); 12 13 // 目标值位于数组中间 14 if (nums[mid] == key) { 15 return mid; 16 } 17 18 // 目标值位于左子数组中 19 else if (key < nums[mid]) { 20 return BinarySearchRec(nums, key, low, mid - 1); 21 } 22 23 // 目标值位于右子数组中 24 else { 25 return BinarySearchRec(nums, key, mid + 1, high); 26 } 27} 28 29int BinarySearch(int nums[], int target, int length) { 30 return BinarySearchRec(nums, target, 0, length - 1); 31} 32 33 34int main() { 35 vector<vector<int> > nums = { 36 {}, {0, 1}, {1, 2, 3}, {-1, 0, 3, 5, 9, 12}, {-1, 0, 3, 5, 9, 12}}; 37 vector<int> sizes = {0, 2, 3, 6, 6}; 38 vector<int> targets = {12, 1, 3, 9, 2}; 39 for (int i = 0; i < nums.size(); i++) { 40 // 自定义函数用于整洁打印列表 41 cout << i + 1 << ". 要搜索的数组: "; 42 PrintList(nums[i]); 43 cout << " 目标值: " << targets[i] << endl; 44 int index = BinarySearch(nums[i].data(), targets[i], sizes[i]); 45 if (index != -1) { 46 cout << " " << targets[i] << " 在数组中存在，索引为 " << index << endl; 47 } else { 48 cout << " " << targets[i] << " 不在数组中，返回值为 " << index << endl; 49 } 50 cout << "------------------------------------------------------------------------------------------------------\n" << endl; 51 } 52}
Java
1// 导入所需函数 2import java.util.*; 3 4class BinarySearch { 5 static int binarySearchRec(int[] nums, int target, int low, int high) { 6 if (low > high) { 7 return -1; 8 } 9 10 // 使用向下取整计算中间位置 11 int mid = low + ((high - low) / 2); 12 13 // 目标值位于数组中间 14 if (nums[mid] == target) { 15 return mid; 16 } 17 18 // 目标值位于左子数组中 19 else if (target < nums[mid]) { 20 return binarySearchRec(nums, target, low, mid - 1); 21 } 22 23 // 目标值位于右子数组中 24 else { 25 return binarySearchRec(nums, target, mid + 1, high); 26 } 27 } 28 29 static int binarySearch(int[] nums, int target) { 30 return binarySearchRec(nums, target, 0, nums.length - 1); 31 } 32 33 public static void main(String[] args) { 34 int[][] numsLists = {{}, {0, 1}, {1, 2, 3}, {-1, 0, 3, 5, 9, 12}, {-1, 0, 3, 5, 9, 12}}; 35 int[] targetList = {12, 1, 3, 9, 2}; 36 for (int i = 0; i < numsLists.length; i++) { 37 int[] nums = numsLists[i]; 38 int target = targetList[i]; 39 int index = binarySearch(nums, target); 40 System.out.println(i + 1 + ". 要搜索的数组: " + Arrays.toString(nums)); 41 System.out.println(" 目标值: " + targetList[i]); 42 if (index != -1) { 43 System.out.println(" " + target + " 在数组中存在，其索引为 " + index); 44 } else { 45 System.out.println(" " + target + " 不在数组中，返回值为 " + index); 46 } 47 System.out.println( 48 "----------------------------------------------------------------------------------------------------\n"); 49 } 50 } 51}
Python
1def binary_search_rec(nums, target, low, high): 2 if low > high: 3 return -1 4 5 # 使用向下取整计算中间位置 6 mid = low + ((high - low) // 2) 7 8 # 目标值位于数组中间 9 if nums[mid] == target: 10 return mid 11 12 # 目标值位于左子数组中 13 elif target < nums[mid]: 14 return binary_search_rec(nums, target, low, mid - 1) 15 16 # 目标值位于右子数组中 17 else: 18 return binary_search_rec(nums, target, mid + 1, high) 19 20def binary_search(nums, target): 21 return binary_search_rec(nums, target, 0, len(nums) - 1) 22 23def main(): 24 nums_lists = [[], [0,1], [1,2,3], [-1,0,3,5,9,12], [-1,0,3,5,9,12]] 25 target_list = [12, 1, 3, 9, 2] 26 for i in range(len(nums_lists)): 27 nums = nums_lists[i] 28 target = target_list[i] 29 index = binary_search(nums, target) 30 print(str(i+1) + ". 要搜索的数组: " + str(nums)) 31 print(" 目标值: " + str(target)) 32 if index != -1: 33 print(" " + str(target) + " 在数组中存在，索引为", index) 34 else: 35 print(" " + str(target) + " 不在数组中，返回值为", index) 36 print("----------------------------------------------------------------------------------------------------\n") 37 38if __name__ == '__main__': 39 main()
JS
1let binarySearchRec = function(nums, target, low, high) { 2 if (low > high) { 3 return -1; 4 } 5 6 // 使用向下取整计算中间位置 7 let mid = low + Math.floor((high - low) / 2); 8 9 // 目标值位于数组中间 10 if (nums[mid] === target) { 11 return mid; 12 } 13 14 // 目标值位于左子数组中 15 else if (target < nums[mid]) { 16 return binarySearchRec(nums, target, low, (mid - 1)); 17 } 18 19 // 目标值位于右子数组中 20 else { 21 return binarySearchRec(nums, target, (mid + 1), high); 22 } 23}; 24 25let binarySearch = function(nums, target) { 26 return binarySearchRec(nums, target, 0, (nums.length - 1)); 27}; 28 29let numsLists = [[], [0,1], [1,2,3], [-1,0,3,5,9,12], [-1,0,3,5,9,12]]; 30let targetList = [12, 1, 3, 9, 2]; 31for(let i=0; i<numsLists.length; i++){ 32 let nums = numsLists[i]; 33 let target = targetList[i]; 34 let index = binarySearch(nums, target); 35 // 使用自定义函数打印格式化数组 36 console.log(i+1 + ". 要搜索的数组: " + printArray(nums)); 37 console.log(" 目标值: " + String(target)); 38 if(index!= -1) 39 console.log(" " + String(target) + " 在数组中存在，索引为", index); 40 else 41 console.log(" " + String(target) + " 不在数组中，返回值为", index); 42 console.log("----------------------------------------------------------------------------------------------------\n"); 43 44}
Ruby
1# BinarySearchRec 是实现递归二分查找算法的辅助函数。 2def binary_search_rec(nums, target, low, high) 3 return -1 if low > high 4 5 # 计算中间位置 6 mid = low + ((high - low) / 2).floor 7 8 # 目标值位于数组中间 9 if nums[mid] == target 10 return mid 11 12 # 目标值位于左子数组中 13 elsif target < nums[mid] 14 return binary_search_rec(nums, target, low, mid - 1) 15 16 # 目标值位于右子数组中 17 else 18 return binary_search_rec(nums, target, mid + 1, high) 19 end 20end 21 22def binary_search(nums, target) 23 return binary_search_rec(nums, target, 0, nums.length() - 1) 24end 25 26 27nums_lists = [[], [0,1], [1,2,3], [-1,0,3,5,9,12], [-1,0,3,5,9,12]] 28target_list = [12, 1, 3, 9, 2] 29nums_lists.length.times do |i| 30 nums = nums_lists[i] 31 target = target_list[i] 32 index = binary_search(nums, target) 33 if index != -1 34 print target.to_s + " 在数组中存在，其索引为 ", index.to_s 35 else 36 print target.to_s, " 不在数组中，返回值为 ", index.to_s 37 end 38 print "\n----------------------------------------------------------------------------------------------------\n" 39end
Go
1package main 2import ( 3 "fmt" 4 "strconv" 5) 6 7/* BinarySearchRec 是实现递归二分查找算法的辅助函数。 */ 8func BinarySearchRec(nums []int, target int, low int, high int) int { 9 if low > high { 10 return -1 11 } 12 // 使用向下取整计算中间位置 13 mid := low + (high-low)/2 14 15 if target == nums[mid] { 16 // 目标值位于数组中间 17 return mid 18 } else if target < nums[mid] { 19 // 目标值位于左子数组中 20 return BinarySearchRec(nums, target, low, mid-1) 21 } else { 22 // 目标值位于右子数组中 23 return BinarySearchRec(nums, target, mid+1, high) 24 } 25} 26 27func BinarySearch(nums []int, target int) int { 28 return BinarySearchRec(nums, target, 0, len(nums)-1) 29} 30 31/* ArrayToString 用于将整数数组转换为字符串。 32该函数作为辅助函数，在主函数中用于打印目的。 */ 33func ArrayToString(nums []int) string{ 34 if len(nums) == 0 { 35 return "[]" 36 } 37 res := "[" 38 for _, num := range nums { 39 res += strconv.Itoa(num) + ", " 40 } 41 res += "]" 42 return res[:len(res) - 3] + "]" 43} 44 45func main() { 46 numsLists := [][]int{ 47 {}, 48 {0, 1}, 49 {1, 2, 3}, 50 {-1, 0, 3, 5, 9, 12}, 51 {-1, 0, 3, 5, 9, 12}, 52 } 53 54 targetList := []int{12, 1, 3, 9, 2} 55 for i, nums := range numsLists { 56 target := targetList[i] 57 index := BinarySearch(nums, target) 58 fmt.Printf("%d. 要搜索的数组: %s\n", i+1, ArrayToString(nums)) 59 fmt.Printf(" 目标值: %d\n", target) 60 if index != -1 { 61 fmt.Printf(" %d 在数组中存在，索引为 %d\n", target, index) 62 } else { 63 fmt.Printf(" %d 不在数组中，返回值为 %d\n", target, index) 64 } 65 fmt.Printf( 66 "----------------------------------------------------------------------------------------------------\n\n", 67 ) 68 } 69}
时间复杂度
此解法的时间复杂度为对数级，。
空间复杂度
此解法的空间复杂度为对数级，，因为递归方法会占用栈内存。
二分查找的应用
- 搜索引擎：帮助高效地在大型索引数据库中进行搜索。
- 图书馆：在按某种顺序组织的目录中定位书籍。
- 数据库：快速检索已排序数据中的记录。
- 基因组分析：在大型基因数据库中查找序列。
- 电子商务：在已排序的产品列表中进行搜索。