首页 > 代码库 > 二分查找
二分查找
二分查找（Binary Search）
- 给定包含 n 个元素的已排序数组 sorted_array[]，求给定元素 x 的位置。
- 递归方式（Recursive）实现
- 迭代方式（Iterative）实现
- 给定包含 n 个元素的已排序数组 sorted_array[]，求小于等于给定元素 x 的最近位置（Floor Value）。
- 给定包含 n 个元素的已排序数组 sorted_array[]，其中可能包含若干重复的元素，求给定元素 x 重复的次数。
- 给定包含 n 个元素的已排序数组 sorted_array[]，但数组被从中间某未知点翻转为 A[]，求 A[] 数组中的最小元素。
问题定义：
给定包含 n 个元素的已排序数组 sorted_array[]，求给定元素 x 的位置。
最简单直接的办法就是线性查找（Linear Search），从数组的最左端开始，逐个值与 x 进行比较，如果匹配则返回元素位置，如果不匹配则右移一位继续比较，如果比较到末尾仍为找到则返回 -1。由此可知，线性查找的时间复杂度为 O(n)。
1 class Program 2 { 3 static void Main(string[] args) 4 { 5 int[] sorted_array = new int[10] { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }; 6 7 int index = LinearSearch(sorted_array, 6); 8 Console.WriteLine(index); 9 10 Console.ReadKey();11 }12 13 static int LinearSearch(int[] sorted_array, int x)14 {15 for (int i = 0; i < sorted_array.Length; i++)16 {17 if (sorted_array[i] == x)18 {19 return i;20 }21 }22 23 return -1;24 }25 }
二分查找（Binary Search）算法使用了分治法（Divide and Conquer）来不断缩小查找范围，并充分利用已知的信息将查找时间复杂度降低到 O(logn)。
那已知信息就是：数组是已排序的。
这样通过如下步骤可以减少比较次数：
- 将 x 与数组的中间的值进行比较；
- 如果 x 与中间的值相等，则直接返回中间值的位置；
- 如果 x 较小，则若存在必出现在中间值的左侧；
- 如果 x 较大，则若存在必出现在中间值的右侧；
可以通过递归（Recursive）和迭代（Iterative）两种方式来实现。
递归方式（Recursive）实现：
1 static void Main(string[] args) 2 { 3 int[] sorted_array = new int[10] { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }; 4 5 int index = BinarySearchByRecursive( 6 sorted_array, 0, sorted_array.Length, 6); 7 Console.WriteLine(index); 8 9 Console.ReadKey();10 }11 12 static int BinarySearchByRecursive(13 int[] sorted_array,14 int left,15 int right,16 int x)17 {18 if (left <= right)19 {20 int middle = left + (right - left) / 2;21 22 if (x == sorted_array[middle])23 return middle;24 25 if (x < sorted_array[middle])26 return BinarySearchByRecursive(27 sorted_array, left, middle - 1, x);28 29 return BinarySearchByRecursive(30 sorted_array, middle + 1, right, x);31 }32 33 return -1;34 }
迭代方式（Iterative）实现：
1 static void Main(string[] args) 2 { 3 int[] sorted_array = new int[10] { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }; 4 5 int index = BinarySearchByIterative( 6 sorted_array, 0, sorted_array.Length, 6); 7 Console.WriteLine(index); 8 9 Console.ReadKey();10 }11 12 static int BinarySearchByIterative(13 int[] sorted_array,14 int left,15 int right,16 int x)17 {18 while (left <= right)19 {20 int middle = left + (right - left) / 2;21 22 if (x == sorted_array[middle])23 return middle;24 25 if (x < sorted_array[middle])26 right = middle - 1;27 else28 left = middle + 1;29 }30 31 return -1;32 }
从上面的代码可知，在最坏情况下需要 logn + 1 次比较操作。每个迭代周期内进行了 2 次比较，除非成功匹配了元素。现在我们来尝试尽量减少比较操作的数量，在 while 循环内仅进行一次比较。
1 static void Main(string[] args) 2 { 3 int[] sorted_array = new int[10] { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }; 4 5 for (int i = 0; i < sorted_array.Length; i++) 6 { 7 int index = BinarySearchByIterativeWithLessComparison( 8 sorted_array, 0, sorted_array.Length, i); 9 Console.WriteLine(index);10 }11 12 Console.ReadKey();13 }14 15 static int BinarySearchByIterativeWithLessComparison(16 int[] sorted_array,17 int left,18 int right,19 int x)20 {21 int middle;22 23 while (right - left > 1)24 {25 middle = left + (right - left) / 2;26 27 if (sorted_array[middle] <= x)28 left = middle;29 else30 right = middle;31 }32 33 if (sorted_array[left] == x)34 return left;35 else36 return -1;37 }
现在我们通过使用二分查找（Binary Search）来解决一些常见问题。
问题定义：
给定包含 n 个元素的已排序数组 sorted_array[]，求小于等于给定元素 x 的最近位置（Floor Value）。
例如：sorted_array[] = [-1, 2, 3, 5, 6, 8, 9, 10]，x = 7，则 FloorValue = http://www.mamicode.com/6。
这里需要考虑几个边界条件：
- 如果数组内的所有元素都小于 x，则最后一个元素即为 FloorValue。
- 如果数组内的所有元素都大于 x，则实际上不存在 FloorValue，属于异常情况，返回 -1。
1 static void Main(string[] args) 2 { 3 int[] sorted_array = new int[8] { -1, 2, 3, 5, 6, 8, 9, 10 }; 4 5 int index = Floor(sorted_array, -2); 6 Console.WriteLine(index); 7 8 index = Floor(sorted_array, 7); 9 Console.WriteLine(index);10 11 index = Floor(sorted_array, 8);12 Console.WriteLine(index);13 14 index = Floor(sorted_array, 13);15 Console.WriteLine(index);16 17 Console.ReadKey();18 }19 20 static int Floor(21 int[] sorted_array,22 int x)23 {24 if (x < sorted_array[0])25 return -1;26 27 return BinarySearchFloorValue(28 sorted_array, 0, sorted_array.Length, x);29 }30 31 static int BinarySearchFloorValue(32 int[] sorted_array,33 int left,34 int right,35 int x)36 {37 int middle;38 39 while (right - left > 1)40 {41 middle = left + (right - left) / 2;42 43 if (sorted_array[middle] <= x)44 left = middle;45 else46 right = middle;47 }48 49 return sorted_array[left];50 }
问题定义：
给定包含 n 个元素的已排序数组 sorted_array[]，其中可能包含若干重复的元素，求给定元素 x 重复的次数。
由于是已排序数组，则相同的元素肯定是连续的。这样可以通过查找 x 的最左侧出现和 x 的最右侧出现，则中间的部分都是 x，出现次数 = right - left + 1。
例如：例如：sorted_array[] = [-1, 2, 3, 8, 8, 8, 8, 10]，x = 8，则重复的位置为 [8, 8, 8, 8]，则重复次数为 6 - 3 + 1 = 4 次。
1 static void Main(string[] args) 2 { 3 int[] sorted_array = new int[8] { -1, 2, 3, 8, 8, 8, 8, 10 }; 4 5 int count = CountOccurrences(sorted_array, 8); 6 Console.WriteLine(count); 7 8 Console.ReadKey(); 9 }10 11 static int GetLeftPosition(12 int[] sorted_array,13 int left,14 int right,15 int x)16 {17 int middle;18 19 while (right - left > 1)20 {21 middle = left + (right - left) / 2;22 23 if (sorted_array[middle] >= x)24 right = middle;25 else26 left = middle;27 }28 29 return right;30 }31 32 static int GetRightPosition(33 int[] sorted_array,34 int left,35 int right,36 int x)37 {38 int middle;39 40 while (right - left > 1)41 {42 middle = left + (right - left) / 2;43 44 if (sorted_array[middle] <= x)45 left = middle;46 else47 right = middle;48 }49 50 return left;51 }52 53 static int CountOccurrences(54 int[] sorted_array,55 int x)56 {57 int left = GetLeftPosition(sorted_array, -1, sorted_array.Length - 1, x);58 int right = GetRightPosition(sorted_array, 0, sorted_array.Length, x);59 60 return (sorted_array[left] == x && x == sorted_array[right]) ?61 (right - left + 1) : 0;62 }
问题定义：
给定包含 n 个元素的已排序数组 sorted_array[]，但数组被从中间某未知点翻转为 A[]，求 A[] 数组中的最小元素。
实际上数组中的最小元素 x 将数组分成了左右两侧，左侧的大于 x，右侧的也大于 x。
1 static void Main(string[] args) 2 { 3 int[] A = new int[8] { 6, 7, 8, 9, 10, 2, 3, 4 }; 4 5 int minimum = BinarySearchIndexOfMinimumRotatedArray( 6 A, 0, A.Length - 1); 7 Console.WriteLine(minimum); 8 9 Console.ReadKey();10 }11 12 static int BinarySearchIndexOfMinimumRotatedArray(13 int[] A,14 int left,15 int right)16 {17 int middle;18 19 if (A[left] <= A[right])20 return left;21 22 while (left <= right)23 {24 if (left == right)25 return left;26 27 middle = left + (right - left) / 2;28 29 if (A[middle] < A[right])30 right = middle;31 else32 left = middle + 1;33 }34 35 return -1;36 }
本文《二分查找》由 Dennis Gao 发表自博客园，未经作者本人同意禁止任何形式的转载，任何自动或人为的爬虫转载行为均为耍流氓。
二分查找
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。