二分查找相比于遍历查找
优点：比较次数少、查找速度快
缺点：只针对于有序数组
思想：
以整型升序数组arr为例，将数组分为两部分：数组大小为size，设置数组下标left、mid、right，初始时分别为首元素下标0、中间元素下表（right-left）/2和最后元素下标 size-1，左部分为left-mid，右部分为 mid-right
设查找值为x，比较x与mid的大小：
1.若x<arr[mid]，则说明查找值x在左部分，只需要在这一部分查找，将左部分作为新的整体区间，right更新为mid-1，mid重新计算，mid=（right+left）/ 2；
2.同理，若x>arr[mid]，则说明查找值x在右部分，只需要在这一部分查找，将右部分作为新的整体区间，left更新为mid+1，mid重新计算，mid=（right+left）/ 2；
3.若x=mid，则查找成功，返回查找值x的下标mid
如此循环，循环条件为 left<=right , 若直到 left>right 仍为查找成功，则说明数组内查找值x不存在，返回-1
int search(int* arr, int size, int x) { int left = 0; int right = size - 1; int mid = (left + right) / 2; while (left <= right) { if (x == arr[mid]) { return mid; } else if (x < arr[mid]) { right = mid - 1; mid = (left + right) / 2; } else if (x > arr[mid]) { left = mid + 1; mid = (left + right) / 2; } } return -1; }
算法优化：优化求mid的方法，原先的算法mid=（left+right）/ 2 ，若left和right是两个2特别大的整数，相加后可能会溢出，因此需要改进
mid = （right - left）/ 2 + left
用大数减去小数得到多余部分，除以2再加上小数就得到两个数的平均数
优化后代码：
int search(int* arr, int size, int x) { int left = 0; int right = size - 1; int mid = (left + right) / 2; while (left <= right) { if (x == arr[mid]) { return mid; } else if (x < arr[mid]) { right = mid - 1; mid = (right - left) / 2 + left; } else if (x > arr[mid]) { left = mid + 1; mid = (right - left) / 2 + left; } } return -1; }
