【2024考研】题解14 | #二分查找-I#

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @param target int整型 
     * @return int整型
     */
    int search(vector<int>& nums, int target) {
        // write code here
        //直接手撕二分
        int left = 0;
        int right = nums.size() - 1;

        while (left <= right) {
            int mid = (left + right) / 2;
            if(nums[mid] == target){
                return mid;
            }
            else if(nums[mid] > target){
                right = mid - 1;
            }
            else{
                left = mid + 1;
            }
        }
        //啥也不是
        return -1;
    }
};

基本算法思想

该算法使用二分查找的思想，在有序数组中查找目标值。

首先初始化左指针left为数组的起始位置，右指针right为数组的结束位置。然后在每次循环中，计算中间位置mid，并将中间位置的值与目标值进行比较。

如果中间位置的值等于目标值，则返回中间位置。

如果中间位置的值小于目标值，则将左指针left更新为中间位置的下一个位置。如

果中间位置的值大于目标值，则将右指针right更新为中间位置的前一个位置。

循环继续直到左指针大于右指针，表示目标值不存在于数组中，返回-1。

时空复杂度

该算法的时间复杂度为O(logn)，其中n是数组的长度。每次循环将搜索范围缩小一半。

空间复杂度为O(1)，只使用了常数级别的额外空间。