c++二分算法

二分算法（Binary Search）是一种在有序数组中查找特定元素的算法。它的基本思想是将待查找的区间一分为二，然后判断目标元素在左半区间还是右半区间中，依次缩小查找范围，直到找到目标元素或者确定目标元素不存在。

二分算法可以用递归或循环的方式实现，下面分别介绍这两种方式的实现。

1. 递归实现：

int binarySearchRecursive(int arr[], int target, int left, int right) {
    if (left > right) { // 如果左边界大于右边界，说明目标元素不存在
        return -1;
    }
    
    int mid = left + (right - left) / 2; // 计算中间位置
    
    if (arr[mid] == target) { // 找到目标元素
        return mid;
    } else if (arr[mid] > target) { // 目标元素在左半区间
        return binarySearchRecursive(arr, target, left, mid - 1);
    } else { // 目标元素在右半区间
        return binarySearchRecursive(arr, target, mid + 1, right);
    }
}

1. 循环实现：

int binarySearchIterative(int arr[], int target, int left, int right) {
    while (left <= right) { // 当左边界小于等于右边界时循环
        int mid = left + (right - left) / 2; // 计算中间位置
        
        if (arr[mid] == target) { // 找到目标元素
            return mid;
        } else if (arr[mid] > target) { // 目标元素在左半区间
            right = mid - 1;
        } else { // 目标元素在右半区间
            left = mid + 1;
        }
    }
    
    return -1; // 目标元素不存在
}

以上代码中，arr是待查找的有序数组，target是目标元素，left和right分别表示查找范围的左边界和右边界。两种实现方式的时间复杂度均为O(log n)，其中n是数组的大小。

需要注意的是，二分算法只适用于有序数组，如果数组无序，需要先进行排序。另外，二分算法还有一些变种，比如二分查找第一个等于目标元素的位置、二分查找最后一个等于目标元素的位置、二分查找第一个大于等于目标元素的位置、二分查找最后一个小于等于目标元素的位置等。