二分查找算法详解：原理、代码及实例

二分查找算法详解：原理、代码及实例

二分查找算法是一种高效的查找算法，它适用于有序数组。该算法的基本思想是：每次将查找范围缩小一半，直到找到目标元素或查找范围为空。

代码实现及注释

int binarySearch(int size, int target, int left, int right) {
    left = 0; // 将查找范围的左边界初始化为0
    right = size - 1; // 将查找范围的右边界初始化为数组的最后一个元素的下标
    while(left <= right) { // 循环条件为左边界小于等于右边界
        int mid = left + (right - left) / 2; // 计算中间元素的下标
        if(nums[mid] == target) // 如果中间元素等于目标数，则返回中间元素的下标
            return mid;   
        else if (nums[mid] < target) // 如果中间元素小于目标数，则在右半部分继续查找
            left = mid + 1; // 更新左边界为中间元素的右侧
        else if (nums[mid] > target) // 如果中间元素大于目标数，则在左半部分继续查找
            right = mid - 1; // 更新右边界为中间元素的左侧
    }
    return -1; // 如果未找到目标数，则返回-1
}

实例说明

例如，有一个排序好的数组 [1, 3, 5, 7, 9, 11, 13]，现在要查找数字 7 的位置。

1. 首先将左边界 left 设置为 0，右边界 right 设置为 6。
2. 在第一次循环中，计算中间元素的下标 mid 为 (0+6)/2=3，此时 nums[mid]=7，说明 7 在数组中存在，返回 mid=3。
3. 如果要查找数字 8 的位置，中间元素为 nums[mid]=7，8 大于 7，因此在右半部分继续查找，将 left 更新为 mid+1=4，右边界仍然为 6。
4. 在第二次循环中，计算中间元素的下标 mid 为 (4+6)/2=5，此时 nums[mid]=11，8 小于 11，因此在左半部分继续查找，将 right 更新为 mid-1=4，左边界仍然为 4。
5. 在第三次循环中，计算中间元素的下标 mid 为 (4+4)/2=4，此时 nums[mid]=9，8 小于 9，因此在左半部分继续查找，将 right 更新为 mid-1=3，左边界仍然为 4。
6. 此时 left>right，循环结束，说明数组中不存在数字 8，返回 -1。

总结

二分查找算法是一种非常高效的查找算法，它可以将查找范围快速缩小，从而提高查找效率。在实际应用中，二分查找算法常用于有序数组的查找，例如在字典、数据库等数据结构中。