读研以后写AI那些玩意写多了,确实需要练练算法,我现在写个二分查找都出现问题,绷不住了,而且过CSP竞赛是毕业条件,没办法,以后一天刷一个题吧,太忙了
1. 左闭右闭
class Solution {
public://左闭右闭int search(vector<int>& nums, int target) {int left = 0; //最左侧下标int right = nums.size() - 1; //最右侧下标/*注意!!!求解中点是不断地求解,不是求解一次就完成了,我一开始把求解中点写到循环外了,这是错误的*///(错误)int middle = ((right - left) >> 1) + left; //求解中点下标// 两边都能取到,所以用小于等于while(left <= right){// 中点的判断条件是right - left(区间长度)除2(相当于右移1位)再加left(因为区间不一定是从0开始的)int middle = ((right - left) >> 1) + left; //求解中点下标//如果中间值就是target,直接返回中间下标if(target == nums[middle]){return middle;}//如果target大于中间值,向右子列寻找,则left变成middle+1else if(target > nums[middle]){left = middle + 1;}//如果target小于中间值,向左子列寻找,则right变为middle-1(因为是左闭右闭,闭合包括区间端点,所以需要抠除middle)else{right = middle - 1;}}//都过一遍没找到,返回-1return -1;}
};
2. 左闭右开
class Solution {
public://左闭右开int search(vector<int>& nums, int target) {int left = 0; //最左侧下标int right = nums.size(); //这儿一开始我写错了,还以为是nums.size(),右侧是开区间取不到端点,可以直接用nums的size,相当于最后一个元素下标+1//左闭右开while(left < right){// 中点的判断条件是right - left(区间长度)除2(相当于右移1位)再加left(因为区间不一定是从0开始的)int middle = ((right - left) >> 1) + left; //求解中点下标//如果中间值就是target,直接返回中间下标if(target == nums[middle]){return middle;}//如果target大于中间值,向右子列寻找,则left变成middle+1else if(target > nums[middle]){left = middle + 1;}//如果target小于中间值,向左子列寻找,则right变为middle(因为是左闭右开,开区间不包括区间端点,所以直接是middle)else{right = middle;}}//都过一遍没找到,返回-1return -1;}
};