Feedback

C# - Binärsuche innerhalb einer Liste

Veröffentlicht von am 18.07.2008
(1 Bewertungen)
Sucht innerhalb einer Liste (IList) nach einem bestimmten Element.
GFU-Schulungen  [Anzeige]

Visual Studio Team Foundation Server 2017/2015 (TFS) für Projektmitglieder - Kompakt

Nach Teilnahme an dieser Schulung sind Ihnen die Grundlagen von ALM geläufig. Sie planen und steuern Projekte effizient mit dem Visual Studio Team Foundation Server.

Angular mit ASP.NET Core für .NET-Entwickler

.NET ist Ihnen vertraut, als Entwickler verfügen Sie über einschlägige Kenntnisse. In diesem Kurs lernen Sie nun, Angular in .NET-Umgebungen einzusetzen. Sie verstehen das Konzept von Angular und integrieren das clientseitige JS-Framework sicher in.NET-Anwendungen.

namespace System.Collections
{
	/// <summary>
	/// Performs a binary search within any implementation
	/// of <see cref="System.Collections.IList"/>.
	/// </summary>
	public static class IListBinarySearchExtension
	{
		/// <summary>
		/// Searches for an <paramref name="item"/> within the specified <paramref name="list"/>
		/// using the specified <paramref name="comparer"/>.
		/// </summary>
		/// <typeparam name="T">The type of the list.</typeparam>
		/// <param name="list">The list to search in.</param>
		/// <param name="comparer">The function used to compare the list's elements.</param>
		/// <param name="item">The result of the search.</param>
		/// <returns>Returns <b>true</b> on success; <b>false</b> on failure.</returns>
		public static bool BinarySearch<T>(this IList list, Func<T, int> comparer, out T item)
		{
			if (list == null)
				throw new ArgumentNullException("list");
			if (comparer == null)
				throw new ArgumentNullException("comparer");

			return BinarySearch(list, comparer, 0, list.Count - 1, out item);
		}

		/// <summary>
		/// Searches for an <paramref name="item"/> within the specified range of the specified
		/// <paramref name="list"/> using the specified <paramref name="comparer"/>.
		/// </summary>
		/// <typeparam name="T">The type of the list.</typeparam>
		/// <param name="list">The list to search in.</param>
		/// <param name="comparer">The function used to compare the list's elements.</param>
		/// <param name="item">The result of the search.</param>
		/// <param name="min">The lower bound of the search.</param>
		/// <param name="max">The upper bound of the search.</param>
		/// <returns>Returns <b>true</b> on success; <b>false</b> on failure.</returns>
		public static bool BinarySearch<T>(this IList list, Func<T, int> comparer, int min, int max, out T item)
		{
			if (list == null)
				throw new ArgumentNullException("list");
			if (comparer == null)
				throw new ArgumentNullException("comparer");
			if (min < 0 || min >= list.Count)
				throw new ArgumentOutOfRangeException("min");
			if (max < 0 || max >= list.Count)
				throw new ArgumentOutOfRangeException("max");

			while (min <= max)
			{
				int middle = min + ((max - min) / 2);
				int compared = comparer((T)list[middle]);

				if (compared < 0)
				{
					min = middle + 1;
				}
				else if (compared > 0)
				{
					max = middle - 1;
				}
				else
				{
					item = (T)list[middle];
					return true;
				}
			}

			item = default(T);
			return false;
		}
	}
}
Abgelegt unter Binär, Suche, Binärsuche.

1 Kommentare zum Snippet

SpatzenKanonier schrieb am 22.08.2008:
int List<T>.BinarySearch() und Array.BinarySearch() sind dir bekannt?

Die haben auch eine praktischere Konvention des rückgabewertes:
Positive Rückgabewerte bezeichnen eine genaue Übereinstimmung, negative das Bit-Complement (XOR) der Einsortierposition, also, wollte man das gesuchte und nicht gefundene Item aufnehmen, hätte man da gleich den Index, wo es sortiert einzufügen wäre.
 

Logge dich ein, um hier zu kommentieren!