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

704.二分查找

题目

���定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

示例 1:

输入: nums = [-1,0,3,5,9,12], target = 9     输出: 4       解释: 9 出现在 nums 中并且下标为 4     

示例 2:

输入: nums = [-1,0,3,5,9,12], target = 2     输出: -1        解释: 2 不存在 nums 中因此返回 -1        

提示：

• 你可以假设 nums 中的所有元素是不重复的。

• n 将在 [1, 10000]之间。

• nums 的每个元素都将在 [-9999, 9999]之间。

  代码

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

  思路

  小技巧

  int middle = left + ((right - left) / 2);// 防止溢出 等同于(left + right)/2

  关于二分法的区间

  左闭右闭和左闭右开

  在设定循环条件时遵循“有意义”的原则：左闭右闭在right>=left时有意义，左闭右开在right>left时有意义

  在取左右新边界时遵循舍去已比较的中间值

  记录C++中的int关于取整的问题

  浮点数 转 整型 int

   cout