写一下我的思路，大概是对的，详细证明不出来。
设蓝色水壶为A，红色为B
先取一个A1，对所有的B做一次比较，可以将B分为两个部分，一部分大于A1，一部分小于A1
再取一个A2，将B分为三个部分
再取A3，将B分为四个部分
......
假设现在B被分成了k个部分，B1,B2,B3......BK，
每次取Ai，都从B集合的一半处开始比较，比如第一次从K/2处开始
如果小于该部分所有元素，则向前移动，从K/4处开始
如果大于该部分所有元素，则向后移动，从3K/4处开始
最后找到相等的水壶，将该部分分成两块，B被分成K+1个部分
最坏情况，每次都找到B里面最小或者最大的水壶，那只能是Θ(n2)了
转载请注明原文地址: https://ju.6miu.com/read-673361.html
