实习冲刺第三十四天

33.搜索旋转排序数组

整数数组 nums 按升序排列，数组中的值 互不相同 。

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。

给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

示例 1：

输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4

思路详解：

先找到旋转点，通过二分比较，旋转后的数组中，左边段数字一定都大于右边段

然后确定目标值的区间，如果目标值比旋转点大，位于左半段否则位于右半段

最后对目标元素存在的段数进行二分查找，找到返回下标否则返回-1

代码详解：

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int l=0,r=nums.size()-1;//定义边界，用于搜索旋转点
        while(l<r)
        {
            int mid=l+(r-l)/2+1;//取一个旋转点
            if(nums[mid]>=nums[0])l=mid;//旋转点和第一个元素大小比较，如果小说明一定是旋转点，不小于就移动第一个元素
            else r=mid-1;
        }
        if(target>=nums[0])l=0;//如果旋转点元素小于目标元素说明在前半段，这时候将左边界置于0处
        else l=l+1,r=nums.size()-1;//否则取另一侧的边界
        while(l<r)
        {
            int mid=l+(r-l)/2+1;
            if(nums[mid]<=target)l=mid;//二分法重新寻找元素
            else r=mid-1;
        }
        return nums[r]==target?r:-1;
    }
};

面经：

1. volatile关键字有什么作用，他与const有什么区别

编译器通常会做出优化假设，比如它可能会假设在一个没有看似直接的写操作的循环中，变量是不会改变的。如果变量被声明为volatile，编译器将不会做出这样的假设，它会每次都从内存中读取变量的值，而不是使用寄存器中的缓存值。

下面是一个volatile的例子：

volatile int flag = 0;
// 在一个线程中
void threadFunction() {
    while (flag == 0) {
        // 等待，直到flag被另一个线程设置为非0
    }
    // 做一些工作
}
// 在另一个线程中
void anotherThreadFunction() {
    // 做一些工作，然后设置flag
    flag = 1;
}

区别：

volatile关键字

volatile告诉编译器，变量的值可能会在程序的控制之外被改变，例如通过硬件或者并发执行的线程。

使用volatile声明的变量，编译器不会对它进行优化，每次访问变量时都会直接从内存中读取其值。

const关键字

const表示变量的值在初始化后不会改变。

编译器会确保程序不会修改const变量的值，任何尝试修改const变量的操作都会导致编译错误。