查找两个有序数组的公共元素

 1 /*查找两个有序数组的公共元素*/
 2 #include<stdio.h>
 3 #include<stdlib.h>
 4 
 5 void findCommon1(int *arr1, int *arr2, int len1, int len2);
 6 void findCommon2(int *arr1, int *arr2, int len1, int len2);
 7 
 8 
 9 
10 int main()
11 {
12     int arr1[10] = {1,2,3,4,5,6,7,8,9,10};
13     int arr2[5] = {1,3,5,7,9};
14 
15     findCommon2(arr1,arr2,10,5);
16 
17     return 0;
18 }
19 
20 //时间复杂度为O(len1*len2)
21 void findCommon1(int *arr1, int *arr2, int len1, int len2)
22 {
23     int i, j;
24     i = j = 0;
25     while(i < len1 && j < len2)
26     {
27         if(arr1[i] == arr2[j])
28         {
29             printf("%3d",arr1[i]);
30             i++;
31             j++;
32         }
33         else
34             arr1[i] > arr2[j] ? j++ : i++;
35     }
36     printf("
");
37 }
38 
39 //对数组2进行二分查找，时间复杂度为O(len1*lg(len2))
40 void findCommon2(int *arr1, int *arr2, int len1, int len2)
41 {
42     int i, low, mid, high;
43     for(i = 0; i < len1; i++)
44     {
45         low = 0;
46         high = len2 - 1;
47         while(low <= high)
48         {
49             mid = low + (high-low) / 2;
50             if(arr1[i] == arr2[mid])
51             {
52                 printf("%3d",arr1[i]);
53                 break;
54             }
55             else
56                 arr1[i] < arr2[mid] ? (high = mid - 1) : (low = mid + 1);
57         }
58     }//end for()
59 }