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 = NothingAs 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 = NothingAs 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