前言
最近要考试了，重新回顾一下之前学的算法，今天是折半查找，它的平均比较次数是Log2 。
折半查找算法（Binary Search Algorithm），也叫二分查找算法，是一种在有序数组中查找特定值的搜索算法。该算法每次将查找范围折半，将要查找的值与中间位置的值进行比较，根据比较结果决定在哪一半继续查找，直到找到目标值或查找范围缩小到只剩下一个元素为止。.
思想
给定一个有序数组A[0..n-1],和查找值K，返回K在A中的下标。
折半查找需要指定3个指针，left、right、mid，分别是左指针指向下标0，右指针指向元素末尾，mid中间值指向（left+right）/ 2向下取整。
如果A[mid] > K,中间值大于要找的K值，移动right指针，right = mid - 1
如果A[mid] < k,中间值小于要找的K值，移动left指针，left = mid + 1
如果A[mid] == K,则返回 mid
算法实现
public static void Main(string[] args){int[] A = {1,2,3,6,7,11,23,56};int K = 23;Console.WriteLine(Search(A,K));}public static int Search(int[] A,int K){int left = 0;int right = A.Length - 1;while(left <= right){int mid = (left + right) / 2;if(A[mid] == K){ return mid;}else if(A[mid]>K){right = mid - 1;}else{left = mid + 1;}}return -1;}
