二分查找应用：寻找旋转排序数组最小值与缺失数字

二分查找应用：寻找旋转排序数组最小值与缺失数字 | 极客日志

class Solution { public: int findMin(vector<int>& nums) { //选择 nums[n - 1] 作为参照物 int left = 0; int right = nums.size() - 1; while(left < right) { int mid = left + (right - left) / 2; if(nums[mid] > nums[nums.size() - 1]) { left = mid + 1; } else { right = mid; } } return nums[left]; } };

class Solution { public: int findMin(vector<int>& nums) { //选择 nums[0] 作为参照物 int left = 0; int right = nums.size() - 1; while(left < right) { int mid = left + (right - left + 1) / 2; if(nums[mid] >= nums[0]) { left = mid; } else { right = mid - 1; } }//循环结束 left 与 right 相遇的位置是数组最大值， //left+1 位置则是最小值 (数组不是一直递增的情况) if(left == nums.size() - 1)//特殊情况：旋转到数组一直递增 { return nums[0]; } return nums[left + 1]; } };

class Solution { public: int takeAttendance(vector<int>& records) { int left = 0; int right = records.size() - 1; while(left < right) { int mid = left + (right - left) / 2; if(mid >= records[mid]) { left = mid + 1; } else { right = mid; } } if(left == records[left]) { return records[left] + 1; } return records[left] - 1; } };

二分查找应用：寻找旋转排序数组最小值与缺失数字

23.寻找旋转排序数组中的最小值

题目描述：

题目示例：

解法（二分查找）：

算法思路：

C++算法代码：(以 nums[n - 1] 为参照物)

C++算法代码：(以 nums[0] 为参照物)

算法总结及流程解析：

24.0~n-1 中缺失的数字

题目描述：

题目示例：

解法（二分查找）：

算法思路：

C++算法代码：

算法总结及流程解析：

更多推荐文章

相关免费在线工具

二分查找应用：寻找旋转排序数组最小值与缺失数字

23.寻找旋转排序数组中的最小值

题目描述：

题目示例：

解法（二分查找）：

算法思路：

C++算法代码：(以 nums[n - 1] 为参照物)

C++算法代码：(以 nums[0] 为参照物)

算法总结及流程解析：

24.0~n-1 中缺失的数字

题目描述：

题目示例：

解法（二分查找）：

算法思路：

C++算法代码：

算法总结及流程解析：

微信扫一扫，关注极客日志

更多推荐文章

相关免费在线工具