二分查找（Binary Search）
- 给定包含 n 个元素的已排序数组 sorted_array[]，求给定元素 x 的位置。
- 给定包含 n 个元素的已排序数组 sorted_array[]，求小于等于给定元素 x 的最近位置（Floor Value）。
- 给定包含 n 个元素的已排序数组 sorted_array[]，求大于等于给定元素 x 的最近位置（Ceiling Value）。
- 给定包含 n 个元素的已排序数组 sorted_array[]，其中可能包含若干重复的元素，求给定元素 x 重复的次数。
- 给定包含 n 个元素的已排序数组 sorted_array[]，但数组被从中间某未知点翻转为 A[]，求 A[] 数组中的最小元素。
- 给定包含 n 个元素的已排序数组 sorted_array[]，查找其中元素位置等于元素值的位置（Fixed Point）。
- 给定包含 n 个元素的数组 array[]，查找某高点的值大于左右两侧的值的位置（Peak Position）。
给定包含 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）两种方式来实现。
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 }
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 else 28 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 else 30 right = middle; 31 } 32 33 if (sorted_array[left] == x) 34 return left; 35 else 36 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 else 54 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 else 56 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 else 26 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 else 47 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 else 32 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 else 28 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 - 1 29 || array[middle + 1] <= array[middle])) 30 return middle; 31 32 // if middle element is not peak and its left neighbor is greater than it 33 // then left half must have a peak element 34 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 it 38 // then right half must have a peak element 39 else 40 return BinarySearchPeakPosition(array, (middle + 1), right); 41 }
