【LeetCode 算法专题突破】---二分查找（⭐⭐⭐）

前言

���在算法题目的海洋中畅游已久，也曾在算法竞赛中荣获佳绩。然而，我发现自己对于算法的学习，还缺乏一个系统性的总结和归类。尽管我已经涉猎过不少算法类型，但心中仍旧觉得有所欠缺，未能形成完整的算法体系。

因此，我决定踏上这次算法之旅，对常见的算法进行一次全面的梳理与归类。我希望通过这个过程，能够更深入地理解每个经典算法类型的核心知识，加强我的算法能力，并完善自己的算法体系。

同时，我也希望能够将这次学习的成果与你分享，希望对你也有所帮助。让我们一同在算法的世界里探索、成长，共同迎接未来的挑战吧！

1.经典的不能在经典的二分查找（难度⭐）

Leetcode链接：704. 二分查找

1.1题目描述：

     这是一道非常典型的二分查找算法题目,可以说所有要学习二分查找算法的人都必须掌握这道题。题目要求很简单,就是在一个有序数组中查找目标值target。这道题是二分查找算法的入门题和模版题,没有掌握这道题就无法开始学习更复杂的二分查找算法题目。所以这道题对于二分查找算法的理解和掌握非常关键和必要。

1.2代码：

class Solution {public:    int search(vector& nums, int target) {        int left = 0, right = nums.size() - 1;        int mid;        while(left target)            {                right = mid - 1;            }            else if(nums[mid] nums[n])            {                left = mid + 1;            }            else if(nums[mid]  
考虑到题目给出的是一个经过旋转的升序数组，这使得数组不再是有序的，我们需要思考如何运用二分法来解决这一问题。
 
观察到，经过旋转的升序数组可以分为两个递增的区间，一个较大的区间和一个较小的区间。我们可以以区间的最大值作为参照物来进行分析。
 
以最右边的元素为例，它可能是小区间的最大值，也可能是大区间的最大值。如果它是大区间的最大值，这就意味着数组没有经过旋转，因此我们可以先忽略这种特殊情况（这是一个解题的小技巧，特殊情况可以后续再处理）。
 
题目要求找到最小的元素，即小区间的最小值。因此，我们需要找到小区间，并在其中找到最小元素。具体操作如下：
 

• 当 nums[mid] > nums[n] 时，表示中间位置 mid 处于大区间，因此将 left 调整为 mid + 1；
• 当 nums[mid]
• 接着，考虑特殊情况，即当 nums[mid] 这道题是二分法的一个变式，关键在于找到以何为参照系来确定区间的位置，一旦确定，后续的工作就变得相对容易。

  6.点名（难度⭐）

  Leetcode链接：LCR 173. 点名

  6.1题目描述：

  这道题我其实一开始也想不出来，选这道题的目的其实也是想说明，算法积累的重要性，见多识广，才能思路开阔，临危不乱。

  6.2代码：

  class Solution {public:    int takeAttendance(vector& records)     {        int n = records.size() - 1;        int left = 0, right = n, mid = 0;        while(left  
  总结一下：
   
  完成了这六道题目后，相信你对二分查找已经得心应手了～
   
  接下来，继续努力，迎接新的挑战吧～
   
  如果有一天觉得对二分有些生疏了，不妨回来再刷一遍，巩固一下技能～
   
  最后，祝愿你未来的刷题之路愉快顺利～