leecode 704 二分查找

704. 二分查找

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

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

代码：

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

解释：
1. (right - left) >> 1相当于(right - left) / 2，
>>是右移运算符，假设x=5，那么x的二进制为0101，x>>1表示x右移1位，即把最右边一位的1删掉，变为010，此时x=2。
2. middle = (left + right) / 2换成middle = left + (right - left) / 2，再换成middle = left + ((right-left)>>1)。
第一个改进是因为 (left + right) 可能会溢出，第二个改进是为了运算更快。
3. 循坏不变量，区间的定义要小心，建议看卡哥的评论。
4. 题目描述中含有有序数组和无重复元素，都可以想想是否可以使用二分法

35. 搜索插入位置

题目描述：
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
思路：目标值在数组所有元素之前；目标值等于数组中某一个元素；
目标值插入数组中的位置；目标值在数组所有元素之后。
代码如下：二分法

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

ps：循环不变量是指一种在整个循环过程中保持不变的性质，它必须在以下3种情况下均保持不变，且该性质在循环终止后能证明算法的正确性。
（1）初始化（循环初始化后，循环条件测试前）
（2）迭代（第 n 次迭代后，第 n+1 次迭代前）
（3）结束（循环终止即循环条件判断为 false 时）