題目1：153.尋找旋轉(zhuǎn)排序數(shù)組中的最小值

思路分析：

O(logN)來(lái)做，我們就直接二分查找。所以第一步，去尋找其中的二段性。
這里我們可以有兩種方式：以A為參照，以D為參照，來(lái)找C點(diǎn)的值。

思路1：二分查找：以A為參照

以A為參照：

1. 二段性：[A-B段都大于等于A][C-D段都小于A]

2. 迭代：C點(diǎn)在left外，所以left=mid+1，C在right內(nèi)，所以right=mid，沒(méi)有-1上面就不用+1，mid=left+(right-left)/2

特殊情況：翻轉(zhuǎn)后剛好是原來(lái)的升序數(shù)組，此時(shí)以A為參照會(huì)把該數(shù)組當(dāng)成全部A-B段，會(huì)不斷向外找，直到left<right不成立而結(jié)束，該情況需要特殊處理。

代碼實(shí)現(xiàn)：

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

思路2：二分查找，以D為參照

以C為參照：

1. 二段性：[A-B段都大于D][C-D段都小于等于D]

2. 迭代：C點(diǎn)在left外，所以left=mid+1，C在right內(nèi)，所以right=mid，沒(méi)有-1上面就不用+1，mid=left+(right-left)/2

無(wú)特殊情況：若翻轉(zhuǎn)后剛好是原來(lái)的升序數(shù)組，會(huì)把整個(gè)數(shù)組當(dāng)成C-D段，以D為參照，會(huì)往下找，就可以找到C，所以無(wú)需處理

代碼實(shí)現(xiàn)：

class Solution {
public:int findMin(vector<int>& nums) {int left=0,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[right];}
};

LeetCode鏈接：153.尋找旋轉(zhuǎn)排序數(shù)組中的最小值

---

題目2：LCR 173.點(diǎn)名

思路分析：

這道題很簡(jiǎn)單，有很多思路，簡(jiǎn)單的我就直接講一下過(guò)程就OK。

思路1：遍歷查找

遍歷數(shù)組，尋找后一位減前一位的差為2的數(shù)，找到就返回，沒(méi)找到就返回最后一個(gè)數(shù)的下一個(gè)。

思路2：哈希表

分別將數(shù)據(jù)導(dǎo)入哈希表，然后查看哪個(gè)數(shù)的個(gè)數(shù)為零，返回該值。

思路3：異或

數(shù)組records[0]~records[size-1] 與 當(dāng)前數(shù)組各個(gè)數(shù)異或，若結(jié)果為x，則返回x；當(dāng)x等于0時(shí)，需要格外處理，有兩種情況，缺0或者是最后一個(gè)數(shù)后面的數(shù)。需要特殊處理：比對(duì)第一個(gè)數(shù)是不是0就可以。

思路4：求和

數(shù)組records[0]~records[size-1] 的和減去當(dāng)前數(shù)組的和。若結(jié)果為x，則返回x；當(dāng)x等于0時(shí)，需要格外處理，與思路3一樣。

思路5：二分查找

這道題的二分查找很有趣，需要細(xì)節(jié)，能發(fā)現(xiàn)二段性，這題就相當(dāng)簡(jiǎn)單。我們可以發(fā)現(xiàn)這個(gè)升序數(shù)組是從0到n-1，所以我們可以發(fā)現(xiàn)這樣一個(gè)
二段性：[缺失值前面，下標(biāo)與值相同][缺失值后面，下標(biāo)與值不同]，我們找到右區(qū)間的左值的下標(biāo)就是缺失的值。
細(xì)節(jié)處理：當(dāng)所有數(shù)的值和下標(biāo)相同時(shí)，則返回left+1.

代碼實(shí)現(xiàn)：

class Solution {
public:int takeAttendance(vector<int>& records) {int left=0,right=records.size()-1;while(left<right){int mid=left+(right-left)/2;if(mid==records[mid]) left=mid+1;else right=mid;}//處理細(xì)節(jié)：如果缺失的是最后一位if(left==records[left]) return left+1;else return left;}
};

LeetCode鏈接：LCR 173.點(diǎn)名

---

世界舞臺(tái)就是草臺(tái)班子，大膽嘗試吧！！！ ~天天開(kāi)心🎈