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) - Komplett 

JavaScript für .NET-Entwickler

Sie sind .NET-Entwickler und nun stehen Sie vor der Aufgabe, JavaScript in Ihre Arbeit einzubinden. Die Schulung vermittelt Ihnen die JavaScript Grundlagen und die Funktionen der Scriptsprache. Sie wissen, wie objektorientierte Programmierung in JavaScript funktioniert und lernen abschließend Best Practicies Fälle kennen.

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!