二分查找（递归与非递归）

条件

数据存储在有序数组中；数据有序排列。

（以下以升序为例）

递归

输入的参数为数组下标的上下界，这是因为不同层的递归需要区分

int BinarySearchRec(int arr[], int low, int high, int target) { if (arr == NULL || low > high) // 都要考虑点非法输入 return -1; int mid = low + (high - low) / 2; // 避免溢出 int pos = -1; // 为方便记忆，统一以pos表示返回值 if (arr[mid] == target) pos = mid; else if (arr[mid] > target) pos = BinarySearchRec(arr, low, mid - 1, target); else pos = BinarySearchRec(arr, mid + 1, high, target); return pos; }

非递归

非递归输入的参数为数组长度（内部的low, high类比递归方法的不同层传入的参数）

int BinarySearch(int arr[], int len, int target) { if (arr == NULL || len <= 0) return -1; int low = 0, high = len - 1; int pos = -1; while (low <= high) { // ！！！等于号易漏 int mid = low + (high - low) / 2; if (arr[mid] == target) { pos = mid; break; // 此处跳出循环，表示命中 } else if (arr[mid] > target) high = mid - 1; else low = mid + 1; } // 此处跳出循环，表示没有命中，pos维持初始值-1 return pos; }

需要注意的地方

两种方式的参数；非递归while循环的条件。

参考

http://blog.csdn.net/nishiwodeangel/article/details/10748615