【Z的阅读&算法】《如何阅读一本书》+ CC&数组之二分查找

为提升认知而阅读，为锻炼思维而算法

阅读

如何阅读一本书摘录

或许我们对这个世界的了解比以前的人多了，在某种范围内，知识也成了理解的先决条件。这些都是好事。但是，“知识”是否那么必然是“理解”的先决条件，可能和一般人认为的有所差距。有时候，太多的资讯就如同太少的资讯一样，都是一种对理解力的阻碍，从该角度来看，现代的媒体正以压倒性的泛滥资讯阻碍了我们的理解力。

新媒体的观众所面对的是一种复杂的组成——从独创的华丽辞藻到经过审慎挑选的资料和统计——目的都在让人不需要面对困难或努力，很容易整理出“自己”的思绪。但是这些精美包装的资讯效率实在是太高了，让观众根本用不着自己做结论，只需将包装过后的观点装进自己的脑海中，等需要的时候就能直接找到适当的言论，然后无须思考便可表现得宜。

• 作者虽然提出了上述问题，但是却没有立即给出回答。
• Z只好先从个人角度思考解决方案：
  • 当阅览资讯时，应该思考其真实性、正确性、能否经得起实践的检验
  • 如果每次阅览资讯都要思考，那太累了。不如控制资讯的流入方式，尽量从可信度高的来源获取资讯
  • 若资讯来源于教科书、开源公益项目、官方消息、内心诚恳且知识渊博的人，信息可信度往往会更高

crash course

• 对Z来说，阅读书籍和推敲算法都太费脑子，目前选择了crash course作为缓冲
• 推荐顺序：自身好奇 > 哲学、心理学 > 其他
• 上面的官网课程是通过被墙的视频网站播放的，所以无法正常访问
• 国内用户可以通过字幕组网站观看，推荐关闭弹幕以集中注意力
• 观看方式：对Z来说，仅作为入门了解和休息缓冲，通常不做具体记录，如果忘记了回来刷第二次或第N次即可

算法

数组二分查找

• 题目简述：

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

示例 1:
输入: nums = [-1,0,3,5,9,12], target = 9     
输出: 4       
解释: 9 出现在 nums 中并且下标为 4
     
示例 2:
输入: nums = [-1,0,3,5,9,12], target = 2     
输出: -1        
解释: 2 不存在 nums 中因此返回 -1

提示：
nums 中的所有元素是不重复的。
n 将在 [1, 10000]之间。
nums 的每个元素都将在 [-9999, 9999]之间。

• 方法：题目已经明确说明用二分查找
• 前提：二分查找的前提为数组有序且不重复，题目已经满足
• 思考过程的形象表达（脑海浮现/图解/动画）：略
• 思路（文字伪代码）：
  • 比较target与数组中间值，相等则返回中间值下标；由于升序，小于则把左半区间作为新数组；大于则将数组右半区间看作新数组；
  • 比较target与新数组中间值，循环反复，直到找到与target相等的值或者无法形成新数组。
  • 形成的新数组可以用下标区间[left, right]表示，例如刚开始的数组区间为[0, 末元素下标]，左半区间为[0, 中元素下标-1]，右半区间为[中元素下标+1, 末元素下标]。
  • 在循环比较的过程中，若找到target则返回中元素的下标，否则不断修改right或left的值来形成新的左半区间[left, 中元素下标-1]或右半区间[中元素下标+1, right]，当left>right，区间不成立，无法形成新数组，说明没找到与target相等的值，可以返回-1了。
• 根据思路写出代码（C++）：

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

• 特殊情况分析
  • left=right 可行
  • 根据题目取数组长度最小值1 可行
• 优化：int middle = left + ((right - left) / 2);可以防止left + right溢出，但根据题目可知，不存在这种情况
• 时间复杂度分析
  • 考虑最坏情况，middle会不断取新的值（n/2、n/4、n/8直到边界）
  • 设长度为n的数组经过x次循环操作后，middle到达边界，这里边界取1，列出下式
  • n * (1/2)^x = 1 解得 x = log2(n)
  • 去掉底数，得到时间复杂度O(logn)
• 空间复杂度分析
  • 额外开辟的空间是三个整型变量left \ right \ middle，共占用 3 * sizeof(int)字节
  • 以上三个变量都不会随着数组规模n的变化而变化
  • 空间复杂度为O(1)