C++算法练习-day1——704.二分查找

题目来源：. - 力扣（LeetCode）

题目思路分析

二分查找是一种在有序数组中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。

对于本题，我们需要在给定的有序数组nums中查找目标值target，如果找到则返回其索引，否则返回-1。使用二分查找算法可以高效地解决这个问题，其时间复杂度为O(log n)，其中n是数组的大小。

代码实例及注解

实例：

#include <vector>  
  
class Solution {  
public:  
    int search(std::vector<int>& nums, int target) {  
        // 初始化左右指针  
        int left = 0;  
        int right = nums.size() - 1;  
          
        // 当左指针小于等于右指针时，继续搜索  
        while (left <= right) {  
            // 计算中间元素的索引，注意防止(left + right)直接相加可能导致的整数溢出  
            int mid = (right - left) / 2 + left;  
              
            // 如果中间元素等于目标值，返回其索引  
            if (nums[mid] == target) {  
                return mid;  
            }  
            // 如果中间元素大于目标值，说明目标值在左半部分，移动右指针  
            else if (nums[mid] > target) {  
                right = mid - 1;  
            }  
            // 如果中间元素小于目标值，说明目标值在右半部分，移动左指针  
            else {  
                left = mid + 1;  
            }  
        }  
          
        // 如果循环结束仍未找到目标值，返回-1  
        return -1;  
    }  
};

注解：

1. 初始化左右指针：left指向数组的起始位置，right指向数组的末尾位置。
2. 计算中间元素的索引：mid = (right - left) / 2 + left，这种计算方式可以防止(left + right)直接相加可能导致的整数溢出。
3. 比较中间元素与目标值：如果nums[mid] == target，则直接返回mid；如果nums[mid] > target，则说明目标值在左半部分，将right更新为mid - 1；如果nums[mid] < target，则说明目标值在右半部分，将left更新为mid + 1。
4. 返回结果：如果循环结束仍未找到目标值，则返回-1。

知识点摘要

1. 二分查找算法：一种在有序数组中查找某一特定元素的搜索算法，时间复杂度为O(log n)。
2. 整数溢出问题：在计算中间元素的索引时，直接使用(left + right) / 2可能会导致整数溢出。为了避免这个问题，可以使用(right - left) / 2 + left来计算中间元素的索引。
3. 边界条件处理：在二分查找过程中，需要正确处理边界条件，如当left大于right时结束搜索。
4. 有序数组：二分查找算法的前提是数组必须是有序的。如果数组无序，则二分查找算法无法正确工作。

通过本文的讲解，相信读者已经对二分查找算法有了更深入的理解，并能够在实际编程中灵活运用该算法来解决类似的问题。