1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
|
#include <stdio.h>
#include <stdlib.h>
typedef struct List {
int* data;
int length;
int num;
} List;
List* initList(int length) {
List* list = (List*)malloc(sizeof(List));
list -> data = (int*)malloc(sizeof(int) * length);
list -> length = length;
list -> num = 0;
return list;
}
void listAdd(int data, List* list) {
list -> data[list -> num] = data;
list -> num = list -> num + 1;
}
void printList(List* list) {
for (int i = 0; i < list -> num; i++) {
printf("%d ", list -> data[i]);
}
printf("\n");
}
int binarySearch(int key, List* list) {
int start = 0;
int end = list -> num - 1;
int mid;
while (start <= end) {
mid = (start + end) / 2;
if (list -> data[mid] < key) {
start = mid + 1;
}
else if (list -> data[mid] > key) {
end = mid - 1;
}
else
return mid;
}
return -1;
}
int binarySearchRecursion(int key, List* list, int start, int end) {
if (start == end) {
if (list -> data[start] == key) {
return start;
}
else {
return -1;
}
}
int mid = (start + end) / 2;
if (list -> data[mid] < key) {
return binarySearchRecursion(key, list, mid + 1, end);
}
else if (list -> data[mid] > key) {
return binarySearchRecursion(key, list, start, mid - 1);
}
else
return mid;
}
int main() {
List* list = initList(9);
listAdd(1, list);
listAdd(2, list);
listAdd(3, list);
listAdd(4, list);
listAdd(5, list);
listAdd(6, list);
listAdd(7, list);
listAdd(8, list);
listAdd(9, list);
printList(list);
printf("data %d in %d\n", 7, binarySearch(7, list));
printf("data %d in %d\n", 10, binarySearch(10, list));
printf("data %d in %d\n", 1, binarySearch(1, list));
printf("data %d in %d\n", 3, binarySearch(3, list));
printf("data %d in %d\n", 7, binarySearchRecursion(7, list, 0, list -> num - 1));
printf("data %d in %d\n", 10, binarySearchRecursion(10, list, 0, list -> num - 1));
printf("data %d in %d\n", 1, binarySearchRecursion(1, list, 0, list -> num - 1));
printf("data %d in %d\n", 3, binarySearchRecursion(3, list, 0, list -> num - 1));
return 0;
}
|
wechat
alipay
