排序

1. 实现归并排序、快速排序、插入排序、冒泡排序、选择排序、堆排序（选做）（完成leetcode上的返回滑动窗口中的最大值(239)，这是上一期第三天的任务进行保留（涉及队列可以对第二天进行整理复习））

2. 编程实现 O(n) 时间复杂度内找到一组数据的第 K 大元素

int selectKthNum(vector<int> &vi, int low, int up, int k)
{
   int p =  up - low +1;
   if(p<6)
   {
    sort(vi.begin()+low, vi.begin()+up+1);
    return vi[k-1];
   }
   int q = p/5; 
   vector<int> medVec;
   int mid = q/2;
   for (int i = 0; i < 5; i++)
   {
      int m = selectKthNum(vi, i*q, (i+1)*q-1,mid+1);
      medVec.push_back(m);
   }
 
   int mNum = selectKthNum(medVec, 0, 
                      medVec.size()-1,   medVec.size()/2+1);

   vector<int> vec1, vec2, vec3;
   for (int i = low; i <= up; i++)
    {
      if(vi[i] > mNum) vec3.push_back(vi[i]);
      if(vi[i] == mNum) vec2.push_back(vi[i]);
      if(vi[i] < mNum) vec1.push_back(vi[i]);
    }
 
   if(vec1.size()>=k) 
      return selectKthNum(vec1, 0, vec1.size()-1, k);
   else if(vec1.size()+vec2.size()>=k) 
      return mNum;
   else if(vec1.size()+vec2.size()<k) 
      return selectKthNum(vec3, 0, vec3.size()-1, 
                                    k-vec1.size()-vec2.size());
}

二分查找

1. 实现一个有序数组的二分查找算法

2. 实现模糊二分查找算法（比如大于等于给定值的第一个元素）

对应的 LeetCode 练习题

Sqrt(x) （x 的平方根）

英文版：https://leetcode.com/problems/sqrtx/

中文版：https://leetcode-cn.com/problems/sqrtx/

class Solution {
public:
    int mySqrt(int x) {
        if(x <= 0)
            return 0;
        if(x == 1)
            return 1;
        int i = 1, r = x / 2;
        long mid = 0, t = 0;
        while(i <= r) {
            mid = (i + r) / 2;
            t = mid * mid;
            if(t == x)
                return mid;
            else if(t > x)
                r = mid - 1;
            else
                i = mid + 1;
        }
        return r; 

    }
};