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]

VB.NET 2017/2015/2013 Aufbau

Nach dieser Schulung können Sie mittels objektorientierter Modelle in VB.NET 2017/2015/2013 wiederverwendbare Elemente eigenständig erstellen.

ASP.NET Core und Angular Komplett für .NET-Entwickler

Sie  lernen in drei (3) Tagen wie man mit  ASP.NET Core und den Technologien  MVC, Entity Framework, WebAPI und  Razor professionelle sowie moderne  Web-Anwendungsarchitekturen aufbaut.  Die Schulung ist der perfekte  Einstieg um insbesondere datengetriebene  und präsentationsorientierte  Applikationen auf Basis der robusten und  skalierbaren ASP.NET Core  Plattform zu erstellen. Nach der Veranstaltung kennen Sie die Konzepte von Angular und können Angular in neue und bestehende ASP.NET-Anwendungen einsetzen.

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!