剑指 Offer II 068. 查找插入位置（基础二分法）

  1. class Solution {
  2. public:
  3.     int searchInsert(vector<int>& nums, int target) {
  4.         int l = 0, r = nums.size();
  5.         while(l < r) {
  6.             int mid = l + (r-l)/2;
  7.             if(nums[mid] > target) {
  8.                 r = mid;
  9.             } else if(nums[mid] < target) {
  10.                 l = mid + 1;
  11.             } else {
  12.                 return mid;
  13.             }
  14.         }
  15.         return l;
  16.     }
  17. };

剑指 Offer II 069. 山峰数组的顶部（基础二分法）

  1. class Solution {
  2. public:
  3.     int peakIndexInMountainArray(vector<int>& arr) {
  4.         int l = 0, r = arr.size();
  5.         while( l < r) {
  6.             int mid = l + (r-l)/2;
  7.             if(arr[mid] < arr[mid+1]) {
  8.                 l = mid + 1;
  9.             } else {
  10.                 r = mid;
  11.             }
  12.         }
  13.         return l;
  14.     }
  15. };

剑指 Offer II 070. 排序数组中只出现一次的数字（值得看）

  • 如果mid是偶数，则比较nums[mid]和nums[mid+1]是否相等

  • 如果mid是奇数，则比较nums[mid-1]和nums[mid]是相等

    细节

    根据按位异或的性质，可以得到mid和相邻的数之间的如下关系

  • 当mid是奇数时，mid+1 = mid ^ 1

  • 当mid 是偶数时，mid-1 = mid ^ 1

    1. class Solution {
    2. public:
    3.   int singleNonDuplicate(vector<int>& nums) {
    4.       int low = 0, high = nums.size() - 1;
    5.       while (low < high) {
    6.           int mid = (high - low) / 2 + low;
    7.           if (nums[mid] == nums[mid ^ 1]) {
    8.               low = mid + 1;
    9.           } else {
    10.               high = mid;
    11.           }
    12.       }
    13.       return nums[low];
    14.   }
    15. };

    我的写法

    1. class Solution {
    2. public:
    3.   int singleNonDuplicate(vector<int>& nums) {
    4.       int l = 0, r = nums.size();
    5.       while( l < r) {
    6.           int mid = l + (r-l)/2;
    7.           if((mid < r-1&&mid%2==0&&nums[mid] == nums[mid+1])||(mid > 0&&mid%2==1&&nums[mid] == nums[mid-1])) {
    8.               l = mid + 1;
    9.           } else {
    10.               r = mid;
    11.           }
    12.       }
    13.       return nums[l];
    14.   }
    15. };

    剑指 Offer II 071. 按权重生成随机数(二分法+前缀和)

  • 使用前缀和来保存权重

  • 用二分法来查找

  • 返回下标

    C++ 11

    mt19937： 是指2^19937 -1 ，是一种随机数生成算法算法
    random_device{}()：可以生成真随机数，但是只在Linux下有效，因为LInux内核熵池，内核维护了一个熵池用来收集来自设备驱动程序和其它来源的环境噪音。理论上，熵池中的数据是完全随机的，可以实现产生真随机数序列。为跟踪熵池中数据的随机性，内核在将数据加入池的时候将估算数据的随机性，这个过程称作熵估算。熵估算值描述池中包含的随机数位数，其值越大表示池中数据的随机性越好。
    uniform_int_distribution：离散均匀分布类

    1. class Solution {
    2. private:
    3.   mt19937 gen;//mt19937是c++ 11的新特性，是一种随机数算法。
    4.   uniform_int_distribution<int> dis;//离散均匀分布
    5.   vector<int> pre;//前缀和
    6. //真随机数，只在Linux下random_device{}()
    7. public:
    8.   //下面是制定uniform_init_distribution边界
    9.   Solution(vector<int>& w): gen(random_device{}()), dis(1, accumulate(w.begin(), w.end(), 0)) {
    10.       partial_sum(w.begin(), w.end(), back_inserter(pre));//前缀和
    11.   }
    13.   int pickIndex() {
    14.       int x = dis(gen);
    15.       return lower_bound(pre.begin(), pre.end(), x) - pre.begin();//二分法查找
    16.   }
    17. };

    普通写法

    ```cpp

class Solution { private: vector sums; //sums为前缀和数组 int total = 0;

public: Solution(vector& w) { sums.resize(w.size()); for (int i = 0; i < w.size(); ++ i) //构造前缀和数组 { total += w[i]; sums[i] = total; } }

  1. int pickIndex() {
  2.     int rnd = rand() % total;           //生成最大值范围内的随机数
  3.     int left = 0, right = sums.size() - 1;
  5.     while (left < right)                //二分法在前缀和数组中找到第一个大于随机数的元素下标
  6.     {
  7.         int mid = left + (right - left) / 2;
  8.         if (rnd < sums[mid])            
  9.         {
  10.             right = mid;
  11.         }
  12.         else
  13.         {
  14.             left = mid + 1;
  15.         }
  16.     }
  18.     return left;
  19. }

};

<a name="phJHQ"></a>
### [剑指 Offer II 072. 求平方根](https://leetcode-cn.com/problems/jJ0w9p/)
这里注意溢出的问题。
```cpp
class Solution {
public:
    int mySqrt(int x) {
        if(x <= 1) return x;
        int l = 0, r = x;
        while(l < r) {
            long mid = l + (r-l)/2;
            if(pow(mid, 2) < x) {
                l = mid + 1;
            } else if(pow(mid, 2) > x) {
                r = mid;
            } else {
                return mid;
            }
        }
        return l-1;
    }
};

剑指 Offer II 073. 狒狒吃香蕉（巧妙）

虽然目前不清楚狒狒吃香蕉的速度，但是可以得知狒狒的速度肯定需要大于等于 1，同时也要小于等于最大的一堆香蕉数量 max，因为若大于 max 每小时也只能吃一堆，所以更大的速度是没有意义的。这时候可以得到狒狒吃香蕉的速度应该在 [1, max]，可以使用二分查找算法确定速度。取 1 和 max 的中间值 mid，计算出速度为 mid 时吃完香蕉所需时间 t

class Solution {
public:
    int gettime(vector<int>& piles, int speed) {//计算当前速度需要花的时间。
        int ret = 0;
        for(auto pile : piles) {
            ret += pile/speed ;
            if(pile%speed != 0) {
                ret++;
            }
        }
        return ret;
    }
    int minEatingSpeed(vector<int>& piles, int h) {
        int r = *max_element(piles.begin(), piles.end()), l = 1;
        while(l <= r) {//这里的1和r都可能被取到，使用左闭右闭的写法
            int mid = l + (r-l)/2;
            int time = gettime(piles, mid);
            if(time > h) {
                l = mid + 1;
            } else if(time <= h) {//当时间相等的时候还是尽量选择速度小的，因此归于让速度更小的一类
                r = mid - 1;
            }
        }
        return l;
    }
};