剑指offer专项突击版第23天

剑指 Offer II 068. 查找插入位置
很容易想到，找的是第一个大于等于 t a r g e t target target 的位置，可以直接 return lower_bound(nums.begin(), nums.end())-nums.begin() 的，不过没什么意义，这里选择手写二分查找（前提是序列有序或有线性规律）。

class Solution {
public:
    int searchInsert(vector& nums, int target) {
        int l = 0, r = nums.size()-1;
        while(l < r) {
            int mid = l+r>>1;
            if(nums[mid] < target) l = mid+1;
            else r = mid; //最终停在哪个位置应该看 谁等于mid，由于要找的是第一个大于等于target的位置，所以这里让r = mid，就会使得最后停在大于或等于target的位置
        }
        if(l == nums.size()-1 && nums[l] < target) {
            return l + 1;
        }
        return l;
    }
};

剑指 Offer II 069. 山峰数组的顶部

二分查找 O ( l o g N ) O(logN) O(logN)

• 题目保证数据是一个山脉数据，也就是只有一个顶，不存在连续相等的子序列。
• 那么就说明只有两个坡，二分 m i d mid mid ，如果 m i d mid mid 在升序上就让 l l l 移动，否则让 r r r 移动。

class Solution {
public:
    int peakIndexInMountainArray(vector& arr) {
        int l = 0, r = arr.size()-1;
        while(l < r) {
            int mid = l+r>>1;
            if(arr[mid] > arr[mid+1]) r = mid; //降序
            else l = mid+1; //升序
        }
        return l;
    }
};

剑指 Offer II 070. 排序数组中只出现一次的数字
二分查找
核心思想是判断 m i d mid mid 与右边的所有元素个数的奇偶性（左边也行，这里不说明），如果右是偶说明单个的在 m i d mid mid 左边，否则就是右边。

class Solution {
public:
    int singleNonDuplicate(vector& nums) {
        int l = 0, r = nums.size() - 1;
        int n = nums.size();
        while(l < r) {
            int mid = l+r>>1;
            if(mid-1 >= 0 && nums[mid] == nums[mid-1]) {
                mid--; //保持mid在连续两个的最左边那个位置
            } else if(mid+1 < n && nums[mid] != nums[mid+1]) {
                return nums[mid]; //左右两边均不等
            }
            if((r-mid+1) % 2) l = mid+2; //如果右边是奇数数，说明在右边
            else r = mid-1; //否则在左边
        }
        return nums[l];
    }
};

官解更优雅的写法
容易发现如果 n u m s nums nums 都没有单个存在时，偶数位置一定等于右相邻那个，如果存在单个那么单个右边就变成奇数位置等于右相邻，所以这里我们只需将 m i d mid mid 取偶数判断是否等于右相邻，如果等于说明左边都不存在单个，否则就存在。

class Solution {
public:
    int singleNonDuplicate(vector& nums) {
        int low = 0, high = nums.size() - 1;
        while (low < high) {
            int mid = (high - low) / 2 + low;
            mid -= mid & 1; //保持mid为偶数
            if (nums[mid] == nums[mid + 1]) { //说明mid左边没有单个数存在，如果存在就不会相等
                low = mid + 2;
            } else { //mid左边有单个存在，或mid就是单个
                high = mid;
            }
        }
        return nums[low];
    }
};