- #include < iostream > using namespace std;
- // 二分查找找数组下标
- int search(int array[], int low, int high, int target) {
- if (low > high) {
- return - 1;
- }
- int mid = (low + high) / 2;
- if (array[mid] < target) {
- return search(array, low, mid, target);
- } else if (array[mid] > target) {
- return search(array, mid + 1, high, target);
- } else {
- return mid;
- }
- }
- // 迭代版本
- int search2(int array[], int low, int high, int target) {
- while (low <= high) {
- int mid = (low + high) / 2;
- if (array[mid] > target) {
- high = mid - 1;
- } else if (array[mid] < target) {
- low = mid + 1;
- } else {
- return mid;
- }
- }
- return - 1;
- }
- // 左闭右闭区间
- int search3(int array[], int n, int target) {
- int left = 0;
- int right = n - 1; //比如说只有一个情况下
- while (left <= right) { //需要等于号,不然会进不来
- int middle = left + (right - left) >> 1;
- if (target < array[middle]) {
- right = middle - 1;
- } else if (target > array[middle]) {
- left = middle + 1;
- } else {
- return middle;
- }
- }
- return - 1;
- }
- // 左闭右开区间
- int search4(int array[], int n, int target) {
- int left = 0;
- int right = n;
- while (left < right) {
- int middle = left + (right - left) >> 1;
- if (target < array[middle]) {
- right = middle;
- } else if (target > array[middle]) {
- left = middle + 1;
- } else {
- return middle;
- }
- }
- return - 1;
- }
- // 寻找包含某个值的区间[begin,end]
- void search5(int array[], int left, int right, int target, int & begin, int & end) {
- if (left >= right) {
- return;
- }
- int mid = right - (right - begin) / 2;
- if (array[mid] == target) {
- if (mid < begin || begin == -1) {
- begin = mid;
- }
- if (mid > end) {
- end = mid;
- }
- search5(array, left, mid - 1, target, begin, end);
- search5(array, mid + 1, right, target, begin, end);
- } else if (array[mid] > target) {
- search5(array, left, mid - 1, target, begin, end);
- } else {
- search5(array, mid + 1, right, target, begin, end);
- }
- }
- // 求最小的i,使得a[i] = key,其实就是求有重复数值的数组中第一次出现key的下标
- // 重点在于不能要等于,如果(l <= r)这样的话,会导致陷入死循环,因为题目要求计算的是最小下标
- // 并且(a[m] < key),所以导致r=m,l=r,会退出不了
- // 循环退出条件:left == right
- int binary_search_1(int a[], int n, int key) {
- int m,
- l = 0,
- r = n - 1; //闭区间[0, n - 1]
- while (l < r) {
- m = l + ((r - l) >> 1); //向下取整
- cout << ",m " << m;
- if (a[m] < key) l = m + 1;
- else r = m;
- }
- if (a[r] == key) return r;
- return - 1;
- }
- // 同上
- int binary_search_1_1(int a[], int n, int key) {
- int res = (int)(lower_bound(a, a + n, key) - a);
- return (res == n || a[res] != key) ? -1 : res;
- }
- // 求最大的i,使得a[i] = key,其实就是求有重复数值的数组中最后一次出现key的下标
- // 循环退出条件:left == right || left == right - 1
- int binary_search_2(int a[], int n, int key) {
- int m,
- l = 0,
- r = n - 1; //闭区间[0, n - 1]
- while (l < r) {
- m = l + ((r + 1 - l) >> 1); //向上取整
- cout << ",m " << m;
- if (a[m] <= key) l = m;
- else r = m - 1;
- }
- if (a[l] == key) return l;
- return - 1;
- }
- // 同上
- int binary_search_2_2(int a[], int n, int key) {
- int res = (int)(upper_bound(a, a + n, key) - a);
- return (res == 0 || a[res - 1] != key) ? -1 : res;
- }
- // 求最小的i,使得a[i] > key,如果key是最大的了,则返回-1
- // 其实就是求最后一个key的下一个位置的下标
- // 需要(a[m] <= key),这样才能把相等的数值去除掉
- int binary_search_3(int a[], int n, int key) {
- int m,
- l = 0,
- r = n - 1; //闭区间[0, n - 1]
- while (l < r) {
- m = l + ((r - l) >> 1); //向下取整
- cout << ",m " << m;
- if (a[m] <= key) l = m + 1;
- else r = m;
- }
- if (a[r] > key) return r;
- return - 1;
- }
- // 同上
- int binary_search_3_3(int a[], int n, int key) {
- int res = (int)(upper_bound(a, a + n, key) - a);
- return (res == n) ? -1 : res;
- }
- // 求最大的i,使得a[i] < key,如果key已经是最小的了,则返回-1
- // 其实就是求一个key前一个位置的下标
- int binary_search_4(int a[], int n, int key) {
- int m,
- l = 0,
- r = n - 1; //闭区间[0, n - 1]
- while (l < r) {
- m = l + ((r + 1 - l) >> 1); //向上取整
- cout << ",m " << m;
- if (a[m] < key) l = m;
- else r = m - 1;
- }
- if (a[l] < key) return l;
- return - 1;
- }
- // 同上
- int binary_search_4_4(int a[], int n, int key) {
- int res = (int)(lower_bound(a, a + n, key) - a);
- return (res == 0) ? -1 : res;
- }
- int main() {
- int arr[4] = {
- 3,
- 4,
- 5,
- 6
- };
- int result1 = binary_search_1(arr, 4, 5);
- cout << " result1:" << result1 << endl;
- int result2 = binary_search_2(arr, 4, 5);
- cout << " result2:" << result2 << endl;
- int result3 = binary_search_3(arr, 4, 5);
- cout << " result3:" << result3 << endl;
- int result4 = binary_search_4(arr, 4, 5);
- cout << " result4:" << result4 << endl;
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2311423.html