【算法题攻略】二分查找

文章目录一、习题解析1. 二分查找模板题详述二分查找 的解题过程2. 在排序数组中查找元素的第一个和最后一个位置3. 寻找峰值4. 搜索旋转排序数组中的最小值二、练习题1. 点名一、习题解析1. 二分查找模板题详述二分查找 的解题过程题目链接: 704. 二分查找题目描述给定一个 n 个元素有序的升序整型数组 nums 和一个目标值 target 写一个函数搜索 nums 中的 target如果 target 存在返回下标否则返回 -1。你必须编写一个具有 O(log n) 时间复杂度的算法。示例 1:输入: nums [-1,0,3,5,9,12], target 9输出: 4解释: 9 出现在 nums 中并且下标为 4示例 2:输入: nums [-1,0,3,5,9,12], target 2输出: -1解释: 2 不存在 nums 中因此返回 -1提示你可以假设 nums 中的所有元素是不重复的。n 将在 [1, 10000]之间。nums 的每个元素都将在 [-9999, 9999]之间。代码实现classSolution{public:intsearch(vectorintnums,inttarget){intleft0,rightnums.size()-1;inttar_index-1;while(leftright){intmid(leftright)/2;if(nums[mid]target){leftmid1;}elseif(nums[mid]target){rightmid-1;}else{tar_indexmid;break;}}returntar_index;}};2. 在排序数组中查找元素的第一个和最后一个位置题目链接: 34. 在排序数组中查找元素的第一个和最后一个位置题目描述给你一个按照非递减顺序排列的整数数组 nums和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值 target返回 [-1, -1]。你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。示例 1:输入: nums [5,7,7,8,8,10], target 8输出: [3,4]示例 2:输入: nums [5,7,7,8,8,10], target 6输出: [-1,-1]示例 3:输入: nums [], target 0输出: [-1,-1]提示0 nums.length 10^5-10^9 nums[i] 10^9nums 是一个非递减数组-10^9 target 10^9代码实现classSolution{public:vectorintsearchRange(vectorintnums,inttarget){vectorintvec{-1,-1};if(nums.size()0||targetnums.back()||targetnums[0]){returnvec;}// 1. 二分法寻找 目标值在数组的开始位置intleft0,rightnums.size()-1;while(leftright){intmid(leftright)/2;if(nums[mid]target)leftmid1;elseif(nums[mid]target)rightmid;}if(nums[left]target)vec[0]left;// 2. 二分法寻找 目标值在数组的结束位置left0,rightnums.size()-1;while(leftright){intmid(leftright1)/2;if(nums[mid]target)leftmid;elseif(nums[mid]target)rightmid-1;}if(nums[left]target)vec[1]left;returnvec;}};3. 寻找峰值题目链接: 162. 寻找峰值题目描述峰值元素是指其值严格大于左右相邻值的元素。给你一个整数数组 nums找到峰值元素并返回其索引。数组可能包含多个峰值在这种情况下返回 任何一个峰值 所在位置即可。你可以假设 nums[-1] nums[n] -∞ 。你必须实现时间复杂度为 O(log n) 的算法来解决此问题。示例 1:输入: nums [1,2,3,1]输出: 2解释3 是峰值元素你的函数应该返回其索引 2示例 2:输入: nums [1,2,1,3,5,6,4]输出: 1 或 5解释你的函数可以返回索引 1其峰值元素为 2或者返回索引 5 其峰值元素为 6提示1 nums.length 1000-2^31 nums[ i ] 2^31 - 1对于所有有效的 i 都有 nums[ i ] ! nums[ i 1 ]代码实现classSolution{public:intfindPeakElement(vectorintnums){if(nums.size()1)return0;intleft0,rightnums.size()-1;while(leftright){intmid(leftright)/2;if(nums[mid]nums[mid1])leftmid1;elseif(nums[mid]nums[mid1])rightmid;}returnleft;}};4. 搜索旋转排序数组中的最小值题目链接: 153. 寻找旋转排序数组中的最小值题目描述已知一个长度为 n 的数组预先按照升序排列经由 1 到 n 次 旋转 后得到输入数组。例如原数组 nums [0,1,2,4,5,6,7] 在变化后可能得到1若旋转 4 次则可以得到 [4,5,6,7,0,1,2]2若旋转 7 次则可以得到 [0,1,2,4,5,6,7]注意数组 [a[0], a[1], a[2], …, a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], …, a[n-2]] 。给你一个元素值 互不相同 的数组 nums 它原来是一个升序排列的数组并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。示例 1:输入: nums [3,4,5,1,2]输出: 1解释原数组为 [1,2,3,4,5] 旋转 3 次得到输入数组。示例 2:输入: nums [4,5,6,7,0,1,2]输出: 0解释原数组为 [0,1,2,4,5,6,7] 旋转 4 次得到输入数组。示例 3:输入: nums [11,13,15,17]输出: 11解释原数组为 [11,13,15,17] 旋转 4 次得到输入数组。提示n nums.length1 n 5000-5000 nums[i] 5000nums 中的所有整数 互不相同nums 原来是一个升序排序的数组并进行了 1 至 n 次旋转代码实现classSolution{public:intfindMin(vectorintnums){if(nums.size()1)returnnums[0];if(nums[0]nums[1]nums[0]nums.back())returnnums[0];inttargetnums[nums.size()-1];intleft0,rightnums.size()-1;while(leftright){intmid(leftright)/2;if(nums[mid]target)leftmid1;elseif(nums[mid]target)rightmid;}returnnums[left];}};二、练习题1. 点名题目链接: LCR 173. 点名题目描述某班级 n 位同学的学号为 0 ~ n-1。点名结果记录于升序数组 records。假定仅有一位同学缺席请返回他的学号。示例 1:输入: records [0,1,2,3,5]输出: 4示例 2:输入: records [0, 1, 2, 3, 4, 5, 6, 8]输出: 7提示1 records.length 10000