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