-
Notifications
You must be signed in to change notification settings - Fork 8
Expand file tree
/
Copy pathBinarySearch.cpp
More file actions
71 lines (68 loc) · 1.1 KB
/
BinarySearch.cpp
File metadata and controls
71 lines (68 loc) · 1.1 KB
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
#include <iostream.h>
/*l <= r的情况下
*如果比mid小则继续查找小的一边
*如果相等可以直接返回
*如果比mid大则继续查找大的一边
*/
int BinarySearch(int a[], int n, int value)
{
int l = 0;
int r = n - 1;
int mid;
while (l <= r)
{
//mid = l + (r-l)/2;
mid = l + ((r-1)>>1);
if (value < a[mid])
{
r = mid - 1;
}
else if(value == a[mid])
{
return mid;
}
else
{
l = mid + 1;
}
}
return -1;
}
int BinarySearchViaRecursion(int a[], int l, int r, int value)
{
if (l > r)
{
return -1;
}
int mid = l + (r - l) / 2;
if (value < a[mid])
{
return BinarySearchViaRecursion(a, l, mid-1, value);
}
else if (value == a[mid])
{
return mid;
}
else
{
return BinarySearchViaRecursion(a, mid+1, r, value);
}
}
int main()
{
int index, value;
int a[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
cout << "Input the search number:";
cin >> value;
//index = BinarySearch(a, sizeof(a)/sizeof(int), value);
index = BinarySearchViaRecursion(a, 0, sizeof(a)/sizeof(int)-1, value);
if (index == -1)
{
cout<<"Not found!"<<endl;
}
else
{
cout<<"index:"<<index<<endl;
}
return 0;
}