Example1Forloop考虑以下代码的时间复杂度，使用BigThetapublicstaticvoidprintParty(intN){for(inti=1;i<=N;i=i*2){for(intj=0;jhi)return-1;intm=(lo+hi)/2;intcmp=x。比较（排序[m]）；if(cmp<0)returnbinarySearch(sorted,x,lo,m-1);elseif(cmp>0)returnbinarySearch(sorted,x,m+1,hi);elsereturnm;}计算中间位置m时有一个破绽：$$m=\frac{(lo+hi)}{2}$$\(当lo+hi>2^{31}-1\)，即当超过int的最大值时，会发生溢出，导致m变成负数，从而引发数组ArrayIndexOutOfBoundsException，所以找中间位置的解决方案是intmid=low+((high-low)/2);或intmid=(low+high)>>>1;在C和C++里面是没有>>>的，可以写成mid=((unsignedint)low+(unsignedint)high))>>1;细节很重要！参考Example4MergeSort分析归并排序的时间复杂度。归并排序是将一个数组一分为二，再分为四，再分为八，直到缩减为只有一个元素的数组，这是一种典型的排序方式。治理思想然后合并底层的数组。合并过程请参考MergeSortDemo。由于一次合并相当于填充一个大小为N的数组，因此合并过程的时间复杂度在填充次数方面为O(N)。直观分析就是将一个大小为N的数组一分为二，直到缩减为只有1个元素的数组。如果进行K次除法，则\(K=log_{2}N\)然后分析每一层的工作在第一层，需要合并两个大小为N/2的数组，工作量为N。在第二层，由两个N/4数组合并两个N/2数组，即4xN/4。工作量为N...观察每一层的工作量为N，一共有K层，则总工作量为$$f(N)=K\cdotN=Nlog_{2}N$$使用递归数学公式。因此归并排序的时间复杂度为\(\Theta(NlogN)\)
