1 | #Region "Microsoft.VisualBasic::7f9769730745b40a6b433302c768908f, Microsoft.VisualBasic.Core\ComponentModel\ValuePair\TagData\Indexing.vb" |
2 | |
3 | ' Author: |
4 | ' |
5 | ' asuka (amethyst.asuka@gcmodeller.org) |
6 | ' xie (genetics@smrucc.org) |
7 | ' xieguigang (xie.guigang@live.com) |
8 | ' |
9 | ' Copyright (c) 2018 GPL3 Licensed |
10 | ' |
11 | ' |
12 | ' GNU GENERAL PUBLIC LICENSE (GPL3) |
13 | ' |
14 | ' |
15 | ' This program is free software: you can redistribute it and/or modify |
16 | ' it under the terms of the GNU General Public License as published by |
17 | ' the Free Software Foundation, either version 3 of the License, or |
18 | ' (at your option) any later version. |
19 | ' |
20 | ' This program is distributed in the hope that it will be useful, |
21 | ' but WITHOUT ANY WARRANTY; without even the implied warranty of |
22 | ' MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
23 | ' GNU General Public License for more details. |
24 | ' |
25 | ' You should have received a copy of the GNU General Public License |
26 | ' along with this program. If not, see <http://www.gnu.org/licenses/>. |
27 | |
28 | |
29 | |
30 | ' /********************************************************************************/ |
31 | |
32 | ' Summaries: |
33 | |
34 | ' Module IndexingExtensions |
35 | ' |
36 | ' Function: (+2 Overloads) BinarySearch |
37 | ' |
38 | ' |
39 | ' /********************************************************************************/ |
40 | |
41 | #End Region |
42 | |
43 | Imports System.Runtime.CompilerServices |
44 | |
45 | Namespace ComponentModel.TagData |
46 | |
47 | Public Module IndexingExtensions |
48 | |
49 | <MethodImpl(MethodImplOptions.AggressiveInlining)> |
50 | <Extension> |
51 | Public Function BinarySearch(Of K As IComparable(Of K), T)(source As IEnumerable(Of T), |
52 | key As K, |
53 | getKey As Func(Of T, K), |
54 | Optional [default] As T = Nothing) As T |
55 | |
56 | Return source _ |
57 | .OrderBy(getKey) _ |
58 | .ToArray _ |
59 | .BinarySearch(key, getKey, [default]) |
60 | End Function |
61 | |
62 | ''' <summary> |
63 | ''' |
64 | ''' </summary> |
65 | ''' <typeparam name="K"></typeparam> |
66 | ''' <typeparam name="T"></typeparam> |
67 | ''' <param name="inputArray">传入的数组必须是经过升序排序的</param> |
68 | ''' <param name="key"></param> |
69 | ''' <param name="getKey"></param> |
70 | ''' <param name="[default]"></param> |
71 | ''' <returns></returns> |
72 | <Extension> |
73 | Public Function BinarySearch(Of K As IComparable(Of K), T)(inputArray As T(), key As K, getKey As Func(Of T, K), Optional [default] As T = Nothing) As T |
74 | Dim min = 0 |
75 | Dim max = inputArray.Length - 1 |
76 | Dim mid% |
77 | |
78 | Do While min <= max |
79 | [mid] = (min + max) / 2 |
80 | |
81 | If key.CompareTo(getKey(inputArray(mid))) = 0 Then |
82 | Return inputArray(mid) |
83 | ElseIf key.CompareTo(getKey(inputArray(mid))) < 0 Then |
84 | max = mid - 1 |
85 | Else |
86 | min = mid + 1 |
87 | End If |
88 | Loop |
89 | |
90 | Return [default] |
91 | End Function |
92 | End Module |
93 | End Namespace |