第一題 leetcode 704.二分查找

二分法的思路

二分法的思路很簡(jiǎn)單

• 數(shù)組必須有序
• 先查找中間元素進(jìn)行比較
• 得出大小再考慮向左比較還是向右比較

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

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

結(jié)果如下

第二題 leetcode 35.搜索插入位置

題目描述

題目分析

和704題的比較如下

• 依舊需要返回可以搜到的下標(biāo)
• 704搜不到返回-1 本題返回可以插入的位置

代碼示例

class Solution {
public:int searchInsert(vector<int>& nums, int target) {int left = 0;int right = nums.size() - 1;int middle = 0;while(left <= right){middle = left + (right - left) / 2;if(nums[middle]==target){return middle;}else if(nums[middle] < target){left = middle + 1;}else{right = middle - 1;}}// 為何返回left的原因有以下幾點(diǎn)// 我們需要返回一個(gè)正確的有序位置 而且計(jì)算到最后返回-1 的時(shí)候 已有三個(gè)參數(shù) left，middle， rightreturn left;}
};

明確eft的原因從以下幾點(diǎn)來看

• while的限制條件是left大于right的時(shí)候，那么一旦找不到righ會(huì)-1導(dǎo)致left大于right退出while循環(huán)
• 此時(shí)left的位置就是要插入的位置

第三題 leetcode 34.

題目描述

分析

核心就是當(dāng)邊界結(jié)束的時(shí)候left代表的是什么

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

class Solution {
private:int board(vector<int>& nums, int target){int left = 0;int right = nums.size() - 1;int middle = 0;while(left<=right){middle = left + (right-left) / 2;if(nums[middle]<target){left = middle + 1;}else{right = middle - 1;}}return left;// 返回左邊界 即可以查找到的第一個(gè)數(shù)的位置}
public:vector<int> searchRange(vector<int>& nums, int target) {vector<int> res={-1, -1};int start = board(nums, target);// 排除三種情況if(nums.size()==0 || nums[nums.size()-1] < target || nums[start]!=target){return res;}int end = board(nums, target+1)-1;res.clear();res.push_back(start);res.push_back(end);return res;}
};

第四題 leetcode 69

題目描述

分析

說白了也是搜素 只是現(xiàn)在需要不保留小數(shù)的
那么搜素結(jié)束之后的right即是較小的那一個(gè)，另外將特殊情況排除一下

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

class Solution {
public:int mySqrt(int x) {int left = 0;int right = x;int middle = 0;if(x==0){return 0;}if(x==1){return 1;}while(left<=right){middle = left + (right-left) / 2;if(x/middle > middle){left = middle + 1;}else if(x/middle == middle){return middle;}else{right = middle - 1;}}return right;}
};

第五題 leetcode 367.

題目描述

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

class Solution {
public:bool isPerfectSquare(int num) {int left = 1;int right = num;int middle = 0;if(num==1){return true;}while(left<=right){middle = left + (right-left) / 2;if(num/middle > middle){left = middle + 1;}else if((num%middle==0) && (num/middle==middle)){	// 來進(jìn)行判斷是否是平方return true;}else{right = middle - 1;}}return false;}
};