二分查找（Binary Search）
问题定义：
给定包含 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[] = [2, 3, 4, 6, 7, 8, 10, 12]，x = 9，则 FloorValue = 8。
这里需要考虑几个边界条件：
- 如果数组内的所有元素都小于 x，则最后一个元素即为 FloorValue。
- 如果数组内的所有元素都大于 x，则实际上不存在 FloorValue，属于异常情况，返回 -1。
1 static void Main(string[] args) 2 { 3 int[] sorted_array = new int[8] { 2, 2, 4, 6, 7, 8, 10, 12 }; 4 5 int index = -1; 6 7 for (int i = 0; i < sorted_array.Length; i++) 8 { 9 index = Floor(sorted_array, sorted_array[i]);10 Console.WriteLine(index);11 }12 13 index = Floor(sorted_array, 1);14 Console.WriteLine(index);15 16 index = Floor(sorted_array, 5);17 Console.WriteLine(index);18 19 index = Floor(sorted_array, 9);20 Console.WriteLine(index);21 22 index = Floor(sorted_array, 13);23 Console.WriteLine(index);24 25 Console.ReadLine();26 }27 28 static int Floor(29 int[] sorted_array,30 int x)31 {32 if (x < sorted_array[0])33 return -1;34 35 return BinarySearchFloorPosition(36 sorted_array, 0, sorted_array.Length, x);37 }38 39 static int BinarySearchFloorPosition(40 int[] sorted_array,41 int left,42 int right,43 int x)44 {45 int middle;46 47 while (right - left > 1)48 {49 middle = left + (right - left) / 2;50 51 if (sorted_array[middle] <= x)52 left = middle;53 else54 right = middle;55 }56 57 return left;58 } 问题定义：
给定包含 n 个元素的已排序数组 sorted_array[]，求大于等于给定元素 x 的最近位置（Ceiling Value）。
例如：sorted_array[] = [2, 3, 4, 6, 7, 8, 10, 12]，x = 9，则 CeilingValue = 10。
这里需要考虑几个边界条件：
- 如果数组内的所有元素都大于 x，则第一个元素即为 CeilingValue。
- 如果数组内的所有元素都小于 x，则实际上不存在 CeilingValue，属于异常情况，返回 -1。
1 static void Main(string[] args) 2 { 3 int[] sorted_array = new int[8] { 2, 2, 4, 6, 7, 7, 10, 12 }; 4 5 int index = -1; 6 7 for (int i = 0; i < sorted_array.Length; i++) 8 { 9 index = Ceiling(sorted_array, sorted_array[i]);10 Console.WriteLine(index);11 }12 13 index = Ceiling(sorted_array, 1);14 Console.WriteLine(index);15 16 index = Ceiling(sorted_array, 5);17 Console.WriteLine(index);18 19 index = Ceiling(sorted_array, 9);20 Console.WriteLine(index);21 22 index = Ceiling(sorted_array, 13);23 Console.WriteLine(index);24 25 Console.ReadLine();26 }27 28 static int Ceiling(29 int[] sorted_array,30 int x)31 {32 if (x > sorted_array[sorted_array.Length - 1])33 return -1;34 if (x <= sorted_array[0])35 return 0;36 37 return BinarySearchCeilingPosition(38 sorted_array, 0, sorted_array.Length, x);39 }40 41 static int BinarySearchCeilingPosition(42 int[] sorted_array,43 int left,44 int right,45 int x)46 {47 int middle;48 49 while (right - left > 1)50 {51 middle = left + (right - left) / 2;52 53 if (sorted_array[middle] < x)54 left = middle;55 else56 right = middle;57 }58 59 return right;60 } 问题定义：
给定包含 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 } 问题定义：
给定包含 n 个元素的已排序数组 sorted_array[]，查找其中元素位置等于元素值的位置（Fixed Point）。
例如：sorted_array[] = { -10, -1, 0, 3, 10, 11, 30, 50 }，则 Fixed Point = 3。
1 static void Main(string[] args) 2 { 3 int[] sorted_array = new int[8] { -10, -1, 0, 3, 10, 11, 30, 50 }; 4 5 int index = -1; 6 7 index = BinarySearchFixedPosition( 8 sorted_array, 0, sorted_array.Length - 1); 9 Console.WriteLine(index);10 11 Console.ReadLine();12 }13 14 static int BinarySearchFixedPosition(15 int[] array,16 int left,17 int right)18 {19 if (right >= left)20 {21 int middle = (left + right) / 2;22 23 if (middle == array[middle])24 return middle;25 else if (middle > array[middle])26 return BinarySearchFixedPosition(array, (middle + 1), right);27 else28 return BinarySearchFixedPosition(array, left, (middle - 1));29 }30 31 return -1;32 } 问题定义：
给定包含 n 个元素的数组 array[]，查找某高点的值大于左右两侧的值的位置（Peak Position）。
例如：array[] = { 1, 3, 20, 4, 1 }，则 Peak Value = 20，Peak Position = 2。
1 static void Main(string[] args) 2 { 3 int[] array = new int[5] { 1, 3, 20, 4, 1 }; 4 5 int index = -1; 6 7 index = FindPeakPosition(array); 8 Console.WriteLine(index); 9 10 Console.ReadLine();11 }12 13 static int FindPeakPosition(int[] array)14 {15 return BinarySearchPeakPosition(16 array, 0, array.Length - 1);17 }18 19 static int BinarySearchPeakPosition(20 int[] array,21 int left,22 int right)23 {24 int middle = left + (right - left) / 2;25 26 // compare middle element with its neighbors (if neighbors exist)27 if ((middle == 0 || array[middle - 1] <= array[middle])28 && (middle == array.Length - 129 || array[middle + 1] <= array[middle]))30 return middle;31 32 // if middle element is not peak and its left neighbor is greater than it33 // then left half must have a peak element34 else if (middle > 0 && array[middle - 1] > array[middle])35 return BinarySearchPeakPosition(array, left, (middle - 1));36 37 // if middle element is not peak and its right neighbor is greater than it38 // then right half must have a peak element39 else40 return BinarySearchPeakPosition(array, (middle + 1), right);41 }
本文《》由 发表自，未经作者本人同意禁止任何形式的转载，任何自动或人为的爬虫转载行为均为耍流氓。