首页 > 代码库 > 数字在排序数组中出现的次数
数字在排序数组中出现的次数
题目：统计一个数字在排序数组中出现的次数．例如，输入排序数组｛1，2，3，3，3，3，4，5｝和数字３，由于在这个数组中出现了４次，因此输出４．
使用二分查找，基本思想：先查找该数字第一次出现的位置，然后查找该数字最后一次出现的位置．代码如下：
1 #include <stdio.h> 2 #include <stdlib.h> 3 #include <string.h> 4 5 int get_first_k(int *, int, int, int); 6 int get_last_k(int *, int, int, int); 7 8 int main(int argc, char *argv[]) 9 { 10 int a[13] = {1, 2, 5, 5, 5, 5, 16, 20, 23, 24, 28, 30, 43}; 11 int b = 430; 12 int num = 0; 13 int first = 0; 14 int last = 0; 15 16 first = get_first_k(a, b, 0, sizeof(a)/sizeof(int) - 1); 17 if (first == -1) 18 { 19 printf("不存在该数字\n"); 20 return 0; 21 } 22 23 last = get_last_k(a, b, 0, sizeof(a)/sizeof(int) - 1); 24 printf("%d %d\n", first, last); 25 num = last - first + 1; 26 printf("%d\n", num); 27 28 29 return 0; 30 } 31 /* 32 int search(int *a, int target, int p, int r) 33 { 34 if (p <= r) 35 { 36 int mid; 37 38 mid = (p + r) / 2; 39 if (*(a + mid) == target) 40 return 1; 41 else if (*(a + mid) > target) 42 return search(a, target, p, mid - 1); 43 else 44 return search(a, target, mid + 1, r); 45 } 46 return 0; 47 } 48 */ 49 int get_first_k(int *a, int target, int p, int r) 50 { 51 int mid = 0; 52 53 while (p <= r) 54 { 55 mid = (p + r) / 2; 56 if (*(a + mid) == target) 57 { 58 if (mid == 0 || *(a + mid - 1) != target) 59 { 60 return mid; 61 } 62 else 63 { 64 r = mid - 1; 65 } 66 } 67 else if (*(a + mid) > target) 68 { 69 r = mid - 1; 70 } 71 else 72 { 73 p = mid + 1; 74 } 75 76 } 77 78 return -1; 79 } 80 81 int get_last_k(int *a, int target, int p, int r) 82 { 83 int mid = 0; 84 int len = r - p + 1; 85 86 while (p <= r) 87 { 88 mid = (p + r) / 2; 89 if (*(a + mid) == target) 90 { 91 if (mid == len - 1 || *(a + mid + 1) != target) 92 { 93 return mid; 94 } 95 else 96 { 97 p = mid + 1; 98 } 99 }100 else if (*(a + mid) > target)101 {102 r = mid - 1;103 }104 else105 {106 p = mid + 1;107 }108 }109 return -1;110 }
数字在排序数组中出现的次数
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。