题解 | #旋转数组的最小数字#
旋转数组的最小数字
https://www.nowcoder.com/practice/9f3231a991af4f55b95579b44b7a01ba
int bin_search(vector<int>::size_type l_idx, vector<int>::size_type r_idx, vector<int>& arr){
int pivot = arr[0]; // （1）
if(l_idx == r_idx){
return min(arr[l_idx], pivot); // （2）
}
vector<int>::size_type mid_idx = (l_idx + r_idx) / 2;
if(arr[mid_idx] < pivot){
return bin_search(l_idx, mid_idx, arr); // （3）
}
else if(arr[mid_idx] > pivot){
return bin_search(mid_idx+1, r_idx, arr); // （4）
}
else{
return min(bin_search(l_idx, mid_idx, arr), bin_search(mid_idx+1, r_idx, arr)); // （5）
}
}
（1）将最左边的值单独拿出来作为后面向左搜索还是向右搜索的依据
（2）如果l_idx == r_idx，说明搜索到尽头，返回这个值和pivot中小的那个，防止[1,2,3,4,5]这种未旋转的情况
（3）分类讨论，如果中间值小于pivot，说明落在旋转后的右边区域，右边不用再搜索了
（4）如果中间值大于pivot，说明落在旋转后的左边区域，左边不用再搜索了
（5）相等左右都搜索防止[4,3]只有两个值的这种情况
#剑指offer#
广电运通公司福利 101人发布