概念
二分搜索的思想很简单，就是不断的取中间下标，判断其值与目标值的差距，从而不断压缩区间。
题目1 三种代码实现
对于一个有序数组arr，再给定一个整数num，请在arr中找到num这个数出现的最左边的位置。
给定一个数组arr及它的大小n，同时给定num。请返回所求位置。若该元素在数组中未出现，请返回-1。测试样例：[1,2,3,3,4],5,3 返回：2迭代实现思路1
int findPos(vector<int> arr, int n, int num) {if (arr.size() == 0)return -1;int left = 0, right = n - 1, mid;int res = -1;while (left <= right) {mid = (left + right) / 2;if (arr[mid] < num) {left = mid + 1;}else if (arr[mid] > num) {right = mid - 1;}else {//arr[mid] 等于 num，将mid存进res，继续往左找res = mid;right = mid - 1;}}return res;
}迭代实现思路2
跟思路1相比，思路2向左或向右压缩时，当前mid值仍然保留。这就有可能导致死循环，需要在while里加上right-left==1的退出条件。有些场景必须使用这种实现，而不能用思路1，好比求循环有序循环数组（如[7,8,9,1,2,3,4,5]）的最小值，这种情况下，不能mid+1 mid-1，因为对于mid这个点是需要保留的。
int findPos(vector<int> arr, int n, int num) {if (arr.size() == 0)return -1;int left = 0, right = n - 1, mid;int res = -1;while (left < right) {//退出循环的条件if (right - left == 1) {if (arr[right] == num) res = right;if (arr[left] == num) res = left;break;}int mid = (left + right) / 2;if (num < arr[mid]) {right = mid;}else if (num > arr[mid]) {left = mid;}else {res = mid;right = mid;}}return res;
}递归实现
递归实现跟迭代实现的思路是一样的，但由于递归多次函数栈的调用，时间复杂度为O(logn)-O(n)，而且代码并没有因此变得简洁，所以仍然推荐用迭代方式
int findPos(vector<int> arr, int n, int num) {if (arr.size() == 0)return -1;return recur(arr, 0, n - 1, num);
}
int recur(vector<int> &arr, int left, int right, int num) {if (left > right)return -1;int mid = (left + right) / 2;if (arr[mid] < num) {return recur(arr, mid + 1, right, num);}else if (arr[mid] > num) {return recur(arr, left, mid - 1, num);}else {int res = recur(arr, left, mid - 1, num);return (res != -1) ? res : mid;}
}总结
对于二分查找的题目，先看mid这个点是否需要保留，用迭代的思路去写代码，再注意数组迭代到只剩一个、两个元素时的边界的处理。
附加题目：循环有序数组最小值的求法
问题描述
对于一个有序循环数组arr，返回arr中的最小值。
有序循环数组是指，有序数组左边任意长度的部分放到右边去，右边的部分拿到左边来。
比如数组[1,2,3,3,4]，是有序循环数组，[4,1,2,3,3]也是。
给定数组arr及它的大小n，请返回最小值。测试样例：[4,1,2,3,3],5 返回：1代码实现
int getMin(vector<int> arr, int n) {// write code hereif (arr.size() == 0)return -1;if (arr.size() == 1)return arr[0];if (arr[0] < arr[n - 1])return arr[0];int left = 0, right = n - 1, mid;while (left < right) {if (left == right - 1) {break;}if (arr[left] < arr[right]) {return arr[left];}mid = (left + right) / 2;if (arr[mid] < arr[left]) {right = mid;}else if (arr[mid] > arr[right]) {left = mid;}}return arr[left] > arr[right] ? arr[right] : arr[left];
}