算法训练 第四周,新手一周四次训练

一、二分查找

本题给我们提供了一个有n个元素的升序整形数组nums和一个目标值target要求我们找到target在nums数组中的位置并返回下标如果不存在目标值则返回-1。nums中的所有元素不重复n将在[110000]之间nums的每个元素都将在[-99999999]之间。本题我们将不会使用简单的遍历查找方法而是会使用二分查找这种更加高效的方法。

1.二分法

如果要使用二分法我们先得保证被查找的数组是有序的而本题正好是一个升序数组对于这样一个升序数组我们就可以使用二分法了。对于nums数组中的每一个元素都可能会出现三种情况

如果 nums[i]target则下标i即为要寻找的下标

如果 nums[i]>target则target只可能在下标i的左侧

如果 nums[i]<target则target只可能在下标i的右侧。

通过以上特征我们就可以进行二分查找了我们先定义两个指针leftright分别指向数组的左边界和右边界然后在每次查找的过程中我们都选取左右边界的中点mid比较target和nums[mid]的大小如果相等则说明找到了目标值此时我们需要的下标就是mid如果nums[mid]大于target说明目标值在整个查找范围的左半部分此时我们需要将right更新为mid - 1此时就将查找范围缩减了一半如果nums[mid]小于target此时和上述过程同理。我们不断地进行以上过程最终就会找到目标值的下标如果在left大于right之后还没有找到target就说明nums中不存在目标值此时返回-1具体代码如下

int search(int* nums, int numsSize, int target){    int left,right;    left  0;    right  numsSize - 1;    while(left < right)    {        int mid  (left  right)/2;        if(nums[mid] > target)        {            right  mid - 1;        }        else if(nums[mid] < target)        {            left  mid  1;        }        else        {            return mid;        }    }    return -1;}

复杂度分析

时间复杂度O(log⁡n)其中 n 是数组的长度。

空间复杂度O(1)。