给定两个排好序的整型数组，怎么判断它们是否含有相同的数字？

方法一：这个问题不就是遍历一个数组，并在另一个数组中对第一个数组中的每一个整数进行寻找，看它们之间是否有相同的数字。因为整型数组都是经过排序的，所以我们可以采用二分查找方法来寻找。因为遍历一个数组所需的时间复杂度是O(n)（n代表数组的大小），二分查找所需的时间复杂度是O(log n)；故此方法所需的时间复杂度为O(nlog n)。

 1 代码如下： 
 2 bool FindEqualElement1(int a[],size_t dimension1,int b[],size_t dimension2) 
 3 { 
 4 assert(dimension1>0 && dimension2>0); 
 5 size_t i; 
 6 
 7 //如果一个数组中最小元素比另一个数组中最大的元素还要大的话，则两个数组肯定不存在相同元素；
 8 //如果一个数组中最大元素比另一个数组中最小的元素还要小的话，则两个数组肯定不存在相同的元素
 9 if (a[0]>b[dimension2-1] || a[dimension1-1]<b[0]) 
10 { 
11 return false; 
12 } 
13 
14 for (i=0;i<dimension1;i++) 
15 { 
16 
17 int low=0; 
18 int high=dimension2-1; 
19 while(low<=high) 
20 { 
21 
22 int mid=(low+high)/2; 
23 if (a[i]<b[mid]) 
24 { 
25 high=mid-1; 
26 } 
27 else if (a[i]>b[mid]) 
28 { 
29 low=mid+1; 
30 } 
31 else 
32 { 
33 return true; 
34 } 
35 } 
36 
37 } 
38 return false; 
39 }

 

方法二：第一个方法中时间复杂度为O(nlog n)，是不是有点大？那我们有没有别的方法可以降低时间复杂度呢？因为这两个数组都是排好序的，所以我们只要将数组遍历一次就行了。首先我们将每个数组设置一个下标，分别初始化两个数组的起始地址，依次向后遍历。先比较两个数组中的数字，数值小的那个数组的下标向后推进，直到任何一个数组的下标达到数组的末尾时，如果这时候还没有碰到相同的元素，则两个数组中不含有相同的数字。这样我们的时间复杂度就可以缩小到O(n)。

 1 代码实现如下： 
 2 bool FindEqualElement2(int a[],size_t dimension1,int b[],size_t dimension2) 
 3 { 
 4 
 5 assert(dimension1>0 && dimension2>0); 
 6 size_t i=0,j=0; 
 7 
 8 while(i<dimension1 && j<dimension2) 
 9 { 
10 if (a[i]==b[j]) 
11 { 
12 return true; 
13 } 
14 else 
15 { 
16 if (a[i]<b[j]) 
17 { 
18 i++; 
19 } 
20 else if (a[i]>b[j]) 
21 { 
22 j++; 
23 } 
24 } 
25 } 
26 return false; 
27 
28 }