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
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
|
using System;
using System.Collections;
using System.Collections.Generic;
using AlgorithmCollection;
using AlgorithmCollection.Recursion;
namespace AlgorithmCollection.Searching
{
public static class SearchingHelper
{
// 二分搜索，返回索引号
// O(logn)
public static int BinarySearch<T>(T[] dataList, T value) where T : IComparable, IEquatable<T>
{
int n = dataList.Length;
int left = 0;
int right = n - 1;
while (left <= right)
{
int middle = (right + left) / 2;
T midValue = dataList[middle];
if (value.Equals(midValue))
return middle;
if (value.CompareTo(midValue) > 0)
left = middle + 1;
if (value.CompareTo(midValue) < 0)
right = middle - 1;
}
return -1; // 没找到
}
public static int BinarySearch<T>(List<T> dataList, T value) where T : IComparable, IEquatable<T>
{
int index = -1;
RecursionHelper.DivideAndConquer(dataList,
(IList<T> data) =>
{
DivisionDescriptor div = new DivisionDescriptor();
div.left = 0;
div.right = data.Count - 1;
return div;
},
(IList<T> data, DivisionDescriptor div) =>
{
if (data[div.left].CompareTo(value) == 0)
{
index = div.left;
}
},
(IList<T> data, DivisionDescriptor div, out bool bAdhoc) =>
{
int left = div.left;
int right = div.right;
DivisionDescriptor[] division = new DivisionDescriptor[1];
if(right <= left)
{
division[0].left = left;
division[0].right = right;
bAdhoc = true;
return division;
}
int mid = (left + right) / 2;
T midValue = data[mid];
if(midValue.CompareTo(value) > 0)
{
division[0].left = left;
division[0].right = mid - 1;
}
else if (midValue.CompareTo(value) < 0)
{
division[0].left = mid + 1;
division[0].right = right;
}
else
{
division[0].left = mid;
division[0].right = mid;
bAdhoc = true;
return division;
}
bAdhoc = false;
return division;
}
);
return index;
}
// 查找最大值
// O(n)
public static int FindMax<T>(IList<T> dataList) where T : IList, IComparable
{
int max = 0;
for(int i = 0; i < dataList.Count; ++i)
{
if (dataList[i].CompareTo(dataList[max]) > 0)
max = i;
}
return max;
}
// 查找最小值
// O(n)
public static int FindMin<T>(IList<T> dataList) where T : IList, IComparable
{
int min = 0;
for (int i = 0; i < dataList.Count; ++i)
{
if (dataList[i].CompareTo(dataList[min]) < 0)
min = i;
}
return min;
}
public static T Select_Random<T>(IList<T> data, bool descent = false) where T : IList, IComparable
{
return default(T);
}
}
}
|
