问题描述：在两个等长的升序序列中找到两个序列的中位数，设s序列的长度为n(n>=1)，称n/2个位置的数为s的中位数

• 我在这里简单分享下自己对这道题的看法。暴力法这里不谈了，仅仅谈谈教材上的减治法思路，并且是如何实现出bug free的代码，而不会类似于二分查找那样陷入死循环！（下面的=究竟是赋值还是判定相等关系自行判断）

• 教材上的算法思路
  分别求出两个序列的中位数，记为a和b；比较a和b，有下列三种情况：

① a = b：则a即为两个序列的中位数；

② a < b：则中位数只能出现在a和b之间，在序列A中舍弃a之前的元素得到序列A1，在序列B中舍弃b之后的元素得到序列B1；

③ a > b：则中位数只能出现在b和a之间，在序列A中舍弃a之后的元素得到序列A1，在序列B中舍弃b之前的元素得到序列B1；

在A1和B1中分别求出中位数，重复上述过程，直到两个序列中只有一个元素，则较小者即为所求。

• 教材上的伪代码如下
  算法5.1：两个序列中位数SearchMid
  输入：两个长度为n的有序序列A和B
  输出：序列A和B的中位数

• 循环直到序列A和序列B均只有一个元素
  1.1 a = 序列A的中位数；
  1.2 b = 序列B的中位数；
  1.3 比较a和b，执行下面三种情况之一：
  1.3.1 若a=b，则返回a，算法结束；
  1.3.2 若a<b，则在序列A中舍弃a之前的元素，在序列B中舍弃b之后的元素，转步骤1；
  1.3.3 若a>b，则在序列A中舍弃a之后的元素，在序列B中舍弃b之前的元素，转步骤1；

• 序列A和序列B均只有一个元素，返回较小者；

  上述的算法的循环每次使A，B序列长度不断减少，直到满足while循环中的A,B序列各只剩一个元素，最后选择小者为正确答案。但是这个循环真的能做到每次使A,B序列长度减小吗？也就是说假如循环后A,B长度不变的话A,B不可能变成各只剩一个元素，最后永远也不会跳出而陷入死循环！那到底问题出在了哪里呢？
  A： [1,2]
  B： [-1,3]
  假如有这样一个样例，按照上面的算法，取A的中位数下标首尾下标相加除2得下标0，得到A的中位数1，同理取得B的中位数-1，即：
  a=1
  b=-1
  现在a<b，序列A中舍弃a之前的元素，序列B中舍弃B之后的元素，
  现在新的情况为
  A：[1,2]
  B：[-1]
  再求一次a,b
  a=1
  b=-1
  现在a<b，跟上次循环一样序列A中舍弃a之前的元素,序列B中舍弃B之后的元素，boom!这次不管是A还是B一个元素也没扔掉！下次循环仍将是这样的情况，这意味着A，B永远也不会像伪代码描述的那样能够满足退出循环的条件，A，B中都各只剩一个元素，永远循环，根本不能返回我们想要的答案。你也许会说我一眼就看出A,B两个序列的中位数明显就是1嘛！但是计算机不是人，必须按照你写的代码运算从而得到答案。你也许会想到我直接写个if判断从而退出循环嘛！但是如果如果输入这个样例时A,B输入对调呢？你的if还能应付新的样例吗？而且万一有其它样例能使你的样例陷入死循环呢？if也许能解决问题，但这样会使我们的代码臃肿且不够优雅，关键是容易错，所以我们需要从理论上详细推导我们的循环到底在哪里出错了，从而写出真正可用的code

• 我现在详细的推导一下这个循环问题到底出现在哪里
  初始化：
  设序列A: leftA=0,rightA=n-1,midA为A中间元素下标
  设序列B: leftB=0,rightB=n-1,midB为B中间元素下标
  注：n为两个等长序列长度，left,right,mid均为下标
  循环开始 A，B序列初始区间[0,n-1]
  循环：
  while(leftA<=righA&&leftB<=rightB)
  { //这里的循环条件先假定是这样，后面仔细探讨循环条件该填什么
  midA=(leftA+rightA)/2
  a=A[midA]
  midB=(leftB+rightB)/2
  b=B[midB]

  如果 a==b
  return a //两个中位数相等，直接返回

  如果 a<b
  ① 中位数大小范围应为为[a,b]，说明中位数应该位于A中的[midA,rightA]中或者位于B中的[midB,rightB]

  ② 对于A序列，舍弃[leftA,midA-1],序列减小长度为(midA-1)-leftA+1=midA-leftA>=0,当midA-leftA=0时，A的减小长度为0，此时如果不干预将陷入死循环
  当midA-leftA=0时,根据midA的定义,此时midA=(leftA+rightA)/2=leftA
  解得leftA=rightA
  此时使leftA=midA,得到新的A序列[leftA,rightA]

  ③ 对于B序列，舍弃[midB+1,rightB],序列减小长度为rightB-(midB+1)+1
  =rightB-midB>=0,当等式为0时有midB=rightB,根据midB的定义，有
  (leftB+rightB)=rightB，跟② 类似，使这个等式成立的一个解为leftB=rightB
  其实还有一个解是,rightB=leftB+1,为什么呢？其实是这样：
  (rightB+leftB)/2=(leftB+1+leftB)/2=(leftB+leftB)/2+1/2=leftB
  原来是我们没意识到计算机在整数运算中对结果向下取整了，其实也就是直接丢掉了小数
  上面的推导告诉了我们对于B序列，一旦
  (1)rightB=leftB或者 (2)rightB=leftB+1
  B的长度永远也不会减小，对于(2)情况，可以看出此时的B长度为2，里面就两个元素，意味着B在长度为2死就陷入了死循环，这似乎就解释了
  A： [1,2]
  B： [-1,3]
  这个样例为什么会陷入死循环，此时必须干预死循环，（2）出现的比（1）早，只需考虑（2），我们可以在while循环了写leftB+1<right从而避免出现(2)的情况从而跳出循环
  现在使rightB=midB,得到新的B序列 [leftB,rightB]

  如果 a>b
  ① 中位数大小范围应为为[b,a]，说明中位数应该位于A中的[leftA,midA]中或者位于B中的[midB,rightB]
  ② 对于A序列，舍弃区间[midA+1,rightA],减小长度rightA-(midA+1)-1=
  rightA-midA>=0,当leftA==rightA时等式为0
  使rightA=midA，获得新的A序列[leftA,rightA]
  ③ 对于B序列，舍弃区间[leftB,midB-1],减小长度midB-1-leftB+1=
  midB-leftB>=0，当rightB==leftB或rightB==leftB+1时等式为0
  使leftB=midB，获得新的B序列[leftB,rightB]
  }
  终止：
  本来按照教材中的算法伪代码，while循环的条件时直到A,B都仅剩一个元素时跳出，此时while应写成
  while(leftA<rightA || leftB<rightB)即可
  跳出循环后,leftA=rightA&&leftB=rightB
  但是根据上面的分析rightA=leftA+1和rightB=leftA+1时，A,B的长度永远卡死在了2，根本不可能满足跳出循环要求（rightA=leftA和rightB=leftB已经不用管了)因此为了能正确的跳出循环，while应改成
  while(leftA+1<rightA || leftB+1<rightB)
  跳出循环后，leftA+1=rightA&&leftB+1=rightB

• 现在我们讨论一下跳出循环后的答案怎么求
  显然如果初始输入的A,B的长度要么都大于等于2，要么都为1
  当n>=2时，退出循环后A,B两个序列都各只剩2各元素，中位数都在4个候选元素中
  当n==1时，根据上文写的while，不会进入循环，中位数位于2个候选元素中
  对于上面两种情况，一种简单的求中位数的办法是直接合并两个有序序列，由于合并后的序列要么长度为4要么为2，合并是常数级操作，因此时间可以忽略，实际上我也是这样做的

• java示例代码：

class Solution {
    public static void main(String[] args) {
        int[] A = new int[]{1,2};
        int[] B = new int[]{-1,3};
        int temp = searchMid(A, B);
    }

    private static int searchMid(int[] A, int[] B) {
        int leftA = 0, rightA = A.length - 1;//定义leftA,rightA指明序列A的范围
        int leftB = 0, rightB = B.length - 1;//定义leftB,rightB指明序列B的范围
        while (leftA + 1 < rightA || leftB + 1 < rightB) {//跳出循环后leftA+1==rightA&&leftB+1==rightB
            int midA = (leftA + rightA) / 2;
            int a = A[midA];
            int midB = (leftB + rightB) / 2;
            int b = B[midB];
            if (a < b) {
                leftA = midA;//rightA==leftA || rightA=leftA+1时缩减长度为0
                rightB = midB;//rightB==leftB时缩减长度为0
            } else if (a > b) {
                rightA = midA;//rightA==leftA时缩减长度为0
                leftB = midB;//rightB==leftB || rightB==leftB+1时缩减长度为0
            } else {
                return a;
            }
        }
        int[] temp = new int[4];//定义最大长度为4的零时数组，存储2个或4个元素的合并序列
        int index = 0;
        while (leftA <= rightA && leftB <= rightB) {//两个升序序列的合并操作
            if (A[leftA] < B[leftB]) {
                temp[index++] = A[leftA++];
            } else {
                temp[index++] = B[leftB++];
            }
        }
        while (leftA <= rightA) {
            temp[index++] = A[leftA++];
        }
        while (leftB <= rightB) {
            temp[index++] = B[leftB++];
        }
        index--;//index自检后指向合并序列的最后一个元素，方便下标运算求出中位数
        return temp[index / 2];//返回中位数
    }
}

• 时间复杂度，每次循环A,B个减少一半长度，总共循环logn次，最后在2个或4个候选元素得出中位数，常数级操作，故时间复杂度为O(logn)
• 总结：该算法的思路很简单，就是根据两个序列的中位数对比结果，对应抛弃A和B的左或右边序列，在剩下的序列里继续寻找目标，跟二分法类似，思想很简单，但是真正写出bug free的code却不简单，需要仔细地推导才能保证我们的循环是正确的，不会死循环。正巧我的教材上只给出了这个问题的伪代码，并没有给出具体的实现，或许作者自己也只是纸上谈兵并没有去实践过呢？
• 建议：为什么我会想到这个算法会陷入死循环却又能正确的找到解决办法的呢？我为什么会想到这样分析呢？其实是源于我当初写二分查找，始终写不出正确的代码，就是因为循环条件不清晰，像上面一样很容易陷入死循环，没有正确的分析，大学老师当时讲课也只是像教材一样介绍了思想却并没有讲解细节，我很怀疑他自己写不看书能不能正确的写出二分查找算法来。二分查找有很多变种，比如给定一个非降序序列，找出第一个大于或者最后一个大于目标值target的数的下标，看大家能不能写出正确的程序来。这里给大家介绍一个概念：循环不变式，能帮助我们分析自己的程序
  这里贴两个链接，跟上文的中位数问题和二分查找有关，使用了循环不变式这个概念，我觉得很有用，强烈建议大家看看
  利用循环不变式写出正确的二分查找及其衍生算法
  如何写出正确的二分查找？——利用循环不变式理解二分查找及其变体的正确性以及构造方式
  如有错误希望大家指出谢谢！可能有些细节写的不对，但是大家看完我的分析了解了我的思路是应该能分析出我哪里细节写错了。

在计算机中，小数点及其位置是隐含规定的；
有两种隐含方式：定点和浮点

定点数

定点数：小数的位置是固定不变的。定点数又包括定点整数和定点小数。
定点小数：小数点隐含固定在最高数据位的左边，整数位则用于表示符号位，用于表示纯小数。

定点整数：小数点位置隐含固定在最低位之后，最高位为符号位，用于表示纯整数。

浮点数

对于既不是定点整数也不是定点小数的实数，我们可以用浮点数进行表示。

浮点数：小数点的位置由阶码规定，因此是浮动的。用来表示实数。

在计算机中通常把浮点数N分成阶码（用定点整数表示）和尾数（用定点小数表示）两部分来表示。



其中数符为尾数部分的符号位，阶符为阶码部分的符号位。

微信搜索关注「水滴与银弹」公众号，第一时间获取优质技术干货。7年资深后端研发，用简单的方式把技术讲清楚。

我们学习计算机知识时，经常听到「定点数」和「浮点数」，它们之间有什么区别？

平时说到整数，我们就说它是一个定点数，说到小数，就说它是一个浮点数，这种说法是正确的吗？

这篇文章，我们先来看一下，「定点数」究竟与整数和小数有什么关系。

什么是定点数？

要想理解什么是「定点数」，首先，我们需要理解「定点」究竟是什么意思？

我们都知道，数字既包括整数，又包括小数，而小数的精度范围要比整数大得多，所以如果我们想在计算机中，既能表示整数，也能表示小数，关键就在于这个小数点如何表示？

于是人们想出一种方法，即约定计算机中小数点的位置，且这个位置固定不变，小数点前、后的数字，分别用二进制表示，然后组合起来就可以把这个数字在计算机中存储起来，这种表示方式叫做「定点」表示法，用这种方法表示的数字叫做「定点数」。

也就是说「定」是指固定的意思，「点」是指小数点，小数点位置固定即定点数名字的由来。

定点数如何表示数字？

既然定点数只是表示数字的一种方式，那试想，它可以表示整数吗？可以表示小数吗？

答案是肯定的。

定点数如果要表示整数或小数，分为以下三种情况：

1. 纯整数：例如整数100，小数点其实在最后一位，所以忽略不写
2. 纯小数：例如：0.123，小数点固定在最高位
3. 整数+小数：例如1.24、10.34，小数点在指定某个位置

对于前两种情况，纯整数和纯小数，因为小数点固定在最低位和最高位，所以它们用定点数表示时，原理是相同的，只需要把整数部分、小数部分，按照十进制转二进制的规则，分别转换即可。

而对于整数 + 小数的情况，用定点表示时，需要约定小数点的位置，才能在计算机中表示。

定点数表示纯整数和纯小数

听闻不如一见，我们举几个例子。先来看一下定点数如何表示纯整数和纯小数？

对于纯整数100，由于小数点固定在最低位，假定我们以 1 个字节（8 bit）表示，用定点数表示如下（D为十进制缩写，B为二进制缩写）：

100(D) = 01100100(B)

对于纯小数 0.125，由于小数点固定在最高位，同样以 1 个字节（8 bit）表示，用定点数表示如下：

0.125(D) = 0.00100000(B)

从以上例子可以看出，这 2 种情况用定点数表示都比较简单，按照十进制转为二进制规则，即可得到结果。

定点数表示整数+小数

我们再来看定点数如何表示整数 + 小数？

这种情况下，我们需要先约定小数点的位置。

依旧以 1 个字节（8 bit）为例，我们可以约定前 5 位表示整数部分，后 3 位表示小数部分。

对于数字 1.5 用定点数表示就是这样：

1.5(D) = 00001 100(B)

数字 25.125 用定点数表示就是这样：

25.125(D) = 11001 001(B)

这就是用定点数表示一个小数的方式。这里再总结一下这个过程：

1. 在有限的 bit 宽度下，先约定小数点的位置
2. 整数部分和小数部分，分别转换为二进制表示
3. 两部分二进制组合起来，即是结果

在计算机中，用定点数表示一个数字的方法，是不是很简单？

但是有没有发现一个问题，我们约定了前 5 位表示整数部分，后 3 位表示小数部分，此时这个整数部分的二进制最大值只能是 11111，即十进制的 31，小数部分的二进制最大只能表示 0.111，即十进制的 0.875。

如果我们想要表示更大范围的值，怎么办？

1. 扩大 bit 的宽度：例如使用 2 个字节、4 个字节，这样整数部分和小数部分宽度增加，表示范围也就变大了
2. 改变小数点的位置：小数点向后移动，整个数字范围就会扩大，但是小数部分的精度就会越来越低，没有办法表示类似 0.00001 这种高精度的值

由此我们发现，不管如何约定小数点的位置，都会存在以下问题:

• 数值的表示范围有限（小数点越靠左，整个数值范围越小）
• 数值的精度范围有限（小数点越靠右，数值精度越低）

总的来说，就是用定点数表示的小数，不仅数值的范围表示有限，而且其精度也很低。要想解决这 2 个问题，所以人们就提出了使用「浮点数」的方式表示数字，关于浮点数的表示方法，我们会在下一篇文章进行讲解。

虽然定点数表示数字，存在以上说的这些问题，但也只是在表示小数的场景下。如果只是用于表示整数，还是非常方便的。

所以，现代计算机中一般使用定点数来表示整数。

总结

这篇文章我们主要讲了，在计算机中如何使用定点数表示一个数字。总结如下：

1. 定点数是在计算机中表示数字的一种方式，它既可以表示整数，也可以表示小数
2. 在固定 bit 下，约定小数点的位置，然后把整数部分和小数部分分别转换为二进制，就是定点数的结果
3. 受限于小数点的位置，用定点数表示小数时，数值的范围和小数精度是有限的
4. 在现代计算机中，定点数通常用来表示整数，对于高精度的小数，通常用浮点数表示

微信搜索关注「水滴与银弹」公众号，第一时间获取优质技术干货。7年资深后端研发，用简单的方式把技术讲清楚。