704. Binary Search
1.使用start+1 < end，这样保证最后剩两个数
2.mid = start + (end - start)/2，这样避免接近max-int导致的溢出
3.start、end直接等于mid
4.最后比较两个位置
class Solution { public: int search(vector<int>& nums, int target) { if(nums.empty()) return -1; int start = 0; int end = nums.size() - 1; int mid; while(start + 1 < end){ mid = start + (end - start)/2; if(nums[mid] == target) return mid; else if(nums[mid] < target) start = mid; else end = mid; } if(nums[start] == target) return start; if(nums[end] == target) return end; return -1; } };
35. Search Insert Position
从左找第一个大于等于的，从右找第一个小于等于的
注意：分别针对找不到第一个在最后返回的值不同，从左返回的是最后一个位置，从右返回的是第一个位置
class Solution { public: int searchInsert(vector<int>& nums, int target) { if(nums.empty()) return -1; for(int i = 0;i < nums.size();i++){ if(nums[i] >= target) return i; } return nums.size(); } };
leetcode 704. Binary Search 、35. Search Insert Position
原文：https://www.cnblogs.com/ymjyqsx/p/10726300.html