【中等】保研/考研408机试-二分查找（模板题）

二分查找就是在一个有序数组中查找某个值，以首端尾端的中点mid查找对比，mid与要查找的数进行对比，看落在哪个区间，在那个区间重新得到首端和尾端，进而得到新的mid值。

一、模板题

二分查找-I_牛客题霸_牛客网

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

作重注意right的迭代是mid-1； left的迭代是mid+1；  可以理解为：左加右减

二、进阶模板题

如果二分查找是希望返回查找到第一个出现的数，比如[1,2,2,3,4]要查找2，返回的下标应该是1（第二个数），但如果是二分的话就会返回2，这样不满足要求了。

所以需要对if（num[mid]==target）这种情况做一个判断，当出现这个数的适合，前面是不是有相同的？返回相同序列的第一个数即可。

二分查找-II_牛客题霸_牛客网

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