代码随想录算法训练营第一天|704.二分查找、27.移除元素

LeetCode 704.二分查找（C++）

题目链接：704.二分查找 力扣leetCode

二分查找 算法思路：

二分查找需要保证数组为有序数组同时无重复元素，否组无法通过二分查找进行判断（结果无法唯一）

 二分查找通过不断收缩数组，趋近中间值进行，由于有序，可以通过中间值与目标的比较实现

①左闭右闭区间

 1 class Solution {
 2 public:
 3     int search(vector<int>& nums, int target) {
 4         int left =0;
 5         int right =nums.size()-1;//right为最右边，target定义在左闭右闭区间
 6         while (left <=right){//left==right是依然有效
 7             int middle=left+((right-left)/2);//防止溢出，left right middle均为下标值
 8             if(nums[middle]>target){  
 9                 right=middle-1;        //在左区间，[left,middle-1]
10             }
11             else if(nums[middle]<target){
12                 left=middle+1;       //target在右区间，所以[middle+_1,right]
13             }
14             else{
15                 return middle;   //target==mums[middle]，输出下标值
16             }
17         }
18         return-1;//未找到目标值 
19     }
20 };

左闭右闭区间中，left==right 是有意义的，因此在进行循环的边界判断中需要left<=right

▲middle=left+(right-left)/2等同于(left+right)/2，可以防止溢出。原因：当left和right足够大时，left+right后可能导致结果超出范围，如果使用left+(right-left)/2则可以保证middle始终在left和right之间。right-left必定小于数组范围。

②左闭右开区间

左闭右开区间中，left==right是没有意义的，因此判断中用left<right

 1 // 版本二
 2 class Solution {
 3 public:
 4     int search(vector<int>& nums, int target) {
 5         int left = 0;
 6         int right = nums.size(); // 定义target在左闭右开的区间里，即：[left, right)
 7         while (left < right) { // 因为left == right的时候，在[left, right)是无效的空间，所以使用 <
 8             int middle = left + ((right - left) >> 1);
 9             if (nums[middle] > target) {
10                 right = middle; // target 在左区间，在[left, middle)中
11             } else if (nums[middle] < target) {
12                 left = middle + 1; // target 在右区间，在[middle + 1, right)中
13             } else { // nums[middle] == target
14                 return middle; // 数组中找到目标值，直接返回下标
15             }
16         }
17         // 未找到目标值
18         return -1;
19     }
20 };

▲left一定是middle+1，因为middle已经确定≠target，所以要加一进行区间判断。

由于是左闭右开，middle<target即可保证判断区间时不会含上middle，所以right=middle即可，左闭右闭区间需要right=middle-1

LeetCode 27. 移除元素(C++)

题目链接：27.移除元素LeetCode

移除元素算法思路

总结

 leetCode中的时间不用在意，只要保证O(n)最小即可。时间复杂度排序：O(log)<O(n)<O(nlog)<O(n²)。

leetCode是在外部进行main函数调用，因此输出结果时一定是return n; 可以先写出来main中的输出结果，将其return即可。