<?xml version="1.0"?>
<feed xmlns="http://www.w3.org/2005/Atom" xml:lang="en">
	<id>https://wiki.algo.informatik.tu-darmstadt.de/index.php?action=history&amp;feed=atom&amp;title=Array_list%3A_find</id>
	<title>Array list: find - Revision history</title>
	<link rel="self" type="application/atom+xml" href="https://wiki.algo.informatik.tu-darmstadt.de/index.php?action=history&amp;feed=atom&amp;title=Array_list%3A_find"/>
	<link rel="alternate" type="text/html" href="https://wiki.algo.informatik.tu-darmstadt.de/index.php?title=Array_list:_find&amp;action=history"/>
	<updated>2026-11-16T20:56:23Z</updated>
	<subtitle>Revision history for this page on the wiki</subtitle>
	<generator>MediaWiki 1.46.2</generator>
	<entry>
		<id>https://wiki.algo.informatik.tu-darmstadt.de/index.php?title=Array_list:_find&amp;diff=3365&amp;oldid=prev</id>
		<title>Luedecke at 23:10, 19 June 2015</title>
		<link rel="alternate" type="text/html" href="https://wiki.algo.informatik.tu-darmstadt.de/index.php?title=Array_list:_find&amp;diff=3365&amp;oldid=prev"/>
		<updated>2015-06-19T23:10:01Z</updated>

		<summary type="html">&lt;p&gt;&lt;/p&gt;
&lt;table style=&quot;background-color: #fff; color: #202122;&quot; data-mw-interface=&quot;&quot;&gt;
				&lt;col class=&quot;diff-marker&quot; /&gt;
				&lt;col class=&quot;diff-content&quot; /&gt;
				&lt;col class=&quot;diff-marker&quot; /&gt;
				&lt;col class=&quot;diff-content&quot; /&gt;
				&lt;tr class=&quot;diff-title&quot; lang=&quot;en&quot;&gt;
				&lt;td colspan=&quot;2&quot; style=&quot;background-color: #fff; color: #202122; text-align: center;&quot;&gt;← Older revision&lt;/td&gt;
				&lt;td colspan=&quot;2&quot; style=&quot;background-color: #fff; color: #202122; text-align: center;&quot;&gt;Revision as of 23:10, 19 June 2015&lt;/td&gt;
				&lt;/tr&gt;&lt;tr&gt;&lt;td colspan=&quot;2&quot; class=&quot;diff-lineno&quot; id=&quot;mw-diff-left-l1&quot;&gt;Line 1:&lt;/td&gt;
&lt;td colspan=&quot;2&quot; class=&quot;diff-lineno&quot;&gt;Line 1:&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td colspan=&quot;2&quot; class=&quot;diff-side-deleted&quot;&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot; data-marker=&quot;+&quot;&gt;&lt;/td&gt;&lt;td style=&quot;color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;&lt;ins style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;[[Category:Videos]]&lt;/ins&gt;&lt;/div&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td colspan=&quot;2&quot; class=&quot;diff-side-deleted&quot;&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot; data-marker=&quot;+&quot;&gt;&lt;/td&gt;&lt;td style=&quot;color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;&lt;ins style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;{{#ev:youtube|https://www.youtube.com/watch?v=uYTck0kDvl4|500|right||frame}}&lt;/ins&gt;&lt;/div&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td class=&quot;diff-marker&quot;&gt;&lt;/td&gt;&lt;td style=&quot;background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;&amp;#039;&amp;#039;&amp;#039;Algorithmic problem:&amp;#039;&amp;#039;&amp;#039; [[Ordered sequence#Find|Ordered sequence: find]]&lt;/div&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot;&gt;&lt;/td&gt;&lt;td style=&quot;background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;&amp;#039;&amp;#039;&amp;#039;Algorithmic problem:&amp;#039;&amp;#039;&amp;#039; [[Ordered sequence#Find|Ordered sequence: find]]&lt;/div&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td class=&quot;diff-marker&quot;&gt;&lt;/td&gt;&lt;td style=&quot;background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;br&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot;&gt;&lt;/td&gt;&lt;td style=&quot;background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;br&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;/table&gt;</summary>
		<author><name>Luedecke</name></author>
	</entry>
	<entry>
		<id>https://wiki.algo.informatik.tu-darmstadt.de/index.php?title=Array_list:_find&amp;diff=2929&amp;oldid=prev</id>
		<title>Weihe: /* Induction step */</title>
		<link rel="alternate" type="text/html" href="https://wiki.algo.informatik.tu-darmstadt.de/index.php?title=Array_list:_find&amp;diff=2929&amp;oldid=prev"/>
		<updated>2015-05-16T16:10:05Z</updated>

		<summary type="html">&lt;p&gt;&lt;span class=&quot;autocomment&quot;&gt;Induction step&lt;/span&gt;&lt;/p&gt;
&lt;table style=&quot;background-color: #fff; color: #202122;&quot; data-mw-interface=&quot;&quot;&gt;
				&lt;col class=&quot;diff-marker&quot; /&gt;
				&lt;col class=&quot;diff-content&quot; /&gt;
				&lt;col class=&quot;diff-marker&quot; /&gt;
				&lt;col class=&quot;diff-content&quot; /&gt;
				&lt;tr class=&quot;diff-title&quot; lang=&quot;en&quot;&gt;
				&lt;td colspan=&quot;2&quot; style=&quot;background-color: #fff; color: #202122; text-align: center;&quot;&gt;← Older revision&lt;/td&gt;
				&lt;td colspan=&quot;2&quot; style=&quot;background-color: #fff; color: #202122; text-align: center;&quot;&gt;Revision as of 16:10, 16 May 2015&lt;/td&gt;
				&lt;/tr&gt;&lt;tr&gt;&lt;td colspan=&quot;2&quot; class=&quot;diff-lineno&quot; id=&quot;mw-diff-left-l32&quot;&gt;Line 32:&lt;/td&gt;
&lt;td colspan=&quot;2&quot; class=&quot;diff-lineno&quot;&gt;Line 32:&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td class=&quot;diff-marker&quot;&gt;&lt;/td&gt;&lt;td style=&quot;background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;br&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot;&gt;&lt;/td&gt;&lt;td style=&quot;background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;br&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td class=&quot;diff-marker&quot;&gt;&lt;/td&gt;&lt;td style=&quot;background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;&amp;#039;&amp;#039;&amp;#039;Implementation:&amp;#039;&amp;#039;&amp;#039;&lt;/div&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot;&gt;&lt;/td&gt;&lt;td style=&quot;background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;&amp;#039;&amp;#039;&amp;#039;Implementation:&amp;#039;&amp;#039;&amp;#039;&lt;/div&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td class=&quot;diff-marker&quot; data-marker=&quot;−&quot;&gt;&lt;/td&gt;&lt;td style=&quot;color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;# If &amp;lt;math&amp;gt;p=&amp;lt;/math&amp;gt;void, terminate the algorithm and return &lt;del style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;&amp;lt;math&amp;gt;&lt;/del&gt;false&lt;del style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;&amp;lt;/math&amp;gt;&lt;/del&gt;.&lt;/div&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot; data-marker=&quot;+&quot;&gt;&lt;/td&gt;&lt;td style=&quot;color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;# If &amp;lt;math&amp;gt;p=&amp;lt;/math&amp;gt;void, terminate the algorithm and return &lt;ins style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;&#039;&#039;&#039;&lt;/ins&gt;false&lt;ins style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;&#039;&#039;&#039;&lt;/ins&gt;.&lt;/div&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td class=&quot;diff-marker&quot;&gt;&lt;/td&gt;&lt;td style=&quot;background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;# Otherwise, if &amp;lt;math&amp;gt;p.A[j] = \Kappa&amp;lt;/math&amp;gt; for some &amp;lt;math&amp;gt;j \in \{1, \ldots, p.n\}&amp;lt;/math&amp;gt;, terminate the algorithms and return &amp;#039;&amp;#039;&amp;#039;true&amp;#039;&amp;#039;&amp;#039;.&lt;/div&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot;&gt;&lt;/td&gt;&lt;td style=&quot;background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;# Otherwise, if &amp;lt;math&amp;gt;p.A[j] = \Kappa&amp;lt;/math&amp;gt; for some &amp;lt;math&amp;gt;j \in \{1, \ldots, p.n\}&amp;lt;/math&amp;gt;, terminate the algorithms and return &amp;#039;&amp;#039;&amp;#039;true&amp;#039;&amp;#039;&amp;#039;.&lt;/div&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td class=&quot;diff-marker&quot;&gt;&lt;/td&gt;&lt;td style=&quot;background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;# Set &amp;lt;math&amp;gt;p:=p.next&amp;lt;/math&amp;gt;.&lt;/div&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot;&gt;&lt;/td&gt;&lt;td style=&quot;background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;# Set &amp;lt;math&amp;gt;p:=p.next&amp;lt;/math&amp;gt;.&lt;/div&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;/table&gt;</summary>
		<author><name>Weihe</name></author>
	</entry>
	<entry>
		<id>https://wiki.algo.informatik.tu-darmstadt.de/index.php?title=Array_list:_find&amp;diff=2928&amp;oldid=prev</id>
		<title>Weihe: /* Induction step */</title>
		<link rel="alternate" type="text/html" href="https://wiki.algo.informatik.tu-darmstadt.de/index.php?title=Array_list:_find&amp;diff=2928&amp;oldid=prev"/>
		<updated>2015-05-16T16:09:49Z</updated>

		<summary type="html">&lt;p&gt;&lt;span class=&quot;autocomment&quot;&gt;Induction step&lt;/span&gt;&lt;/p&gt;
&lt;table style=&quot;background-color: #fff; color: #202122;&quot; data-mw-interface=&quot;&quot;&gt;
				&lt;col class=&quot;diff-marker&quot; /&gt;
				&lt;col class=&quot;diff-content&quot; /&gt;
				&lt;col class=&quot;diff-marker&quot; /&gt;
				&lt;col class=&quot;diff-content&quot; /&gt;
				&lt;tr class=&quot;diff-title&quot; lang=&quot;en&quot;&gt;
				&lt;td colspan=&quot;2&quot; style=&quot;background-color: #fff; color: #202122; text-align: center;&quot;&gt;← Older revision&lt;/td&gt;
				&lt;td colspan=&quot;2&quot; style=&quot;background-color: #fff; color: #202122; text-align: center;&quot;&gt;Revision as of 16:09, 16 May 2015&lt;/td&gt;
				&lt;/tr&gt;&lt;tr&gt;&lt;td colspan=&quot;2&quot; class=&quot;diff-lineno&quot; id=&quot;mw-diff-left-l33&quot;&gt;Line 33:&lt;/td&gt;
&lt;td colspan=&quot;2&quot; class=&quot;diff-lineno&quot;&gt;Line 33:&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td class=&quot;diff-marker&quot;&gt;&lt;/td&gt;&lt;td style=&quot;background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;&amp;#039;&amp;#039;&amp;#039;Implementation:&amp;#039;&amp;#039;&amp;#039;&lt;/div&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot;&gt;&lt;/td&gt;&lt;td style=&quot;background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;&amp;#039;&amp;#039;&amp;#039;Implementation:&amp;#039;&amp;#039;&amp;#039;&lt;/div&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td class=&quot;diff-marker&quot;&gt;&lt;/td&gt;&lt;td style=&quot;background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;# If &amp;lt;math&amp;gt;p=&amp;lt;/math&amp;gt;void, terminate the algorithm and return &amp;lt;math&amp;gt;false&amp;lt;/math&amp;gt;.&lt;/div&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot;&gt;&lt;/td&gt;&lt;td style=&quot;background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;# If &amp;lt;math&amp;gt;p=&amp;lt;/math&amp;gt;void, terminate the algorithm and return &amp;lt;math&amp;gt;false&amp;lt;/math&amp;gt;.&lt;/div&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td class=&quot;diff-marker&quot; data-marker=&quot;−&quot;&gt;&lt;/td&gt;&lt;td style=&quot;color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;# Otherwise, if &amp;lt;math&amp;gt;p.A[j] = \Kappa&amp;lt;/math&amp;gt; for some &amp;lt;math&amp;gt;j \in \{1, \ldots, p.n\}&amp;lt;/math&amp;gt;, &lt;del style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;set &lt;/del&gt;&amp;lt;math&amp;gt;p:=p.next&amp;lt;/math&amp;gt;.&lt;/div&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot; data-marker=&quot;+&quot;&gt;&lt;/td&gt;&lt;td style=&quot;color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;# Otherwise, if &amp;lt;math&amp;gt;p.A[j] = \Kappa&amp;lt;/math&amp;gt; for some &amp;lt;math&amp;gt;j \in \{1, \ldots, p.n\}&amp;lt;/math&amp;gt;, &lt;ins style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;terminate the algorithms and return &#039;&#039;&#039;true&#039;&#039;&#039;.&lt;/ins&gt;&lt;/div&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td colspan=&quot;2&quot; class=&quot;diff-side-deleted&quot;&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot; data-marker=&quot;+&quot;&gt;&lt;/td&gt;&lt;td style=&quot;color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;&lt;ins style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;# Set &lt;/ins&gt;&amp;lt;math&amp;gt;p:=p.next&amp;lt;/math&amp;gt;.&lt;/div&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td class=&quot;diff-marker&quot;&gt;&lt;/td&gt;&lt;td style=&quot;background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;br&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot;&gt;&lt;/td&gt;&lt;td style=&quot;background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;br&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td class=&quot;diff-marker&quot;&gt;&lt;/td&gt;&lt;td style=&quot;background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;&amp;#039;&amp;#039;&amp;#039;Correctness:&amp;#039;&amp;#039;&amp;#039; Obvious.&lt;/div&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot;&gt;&lt;/td&gt;&lt;td style=&quot;background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;&amp;#039;&amp;#039;&amp;#039;Correctness:&amp;#039;&amp;#039;&amp;#039; Obvious.&lt;/div&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;/table&gt;</summary>
		<author><name>Weihe</name></author>
	</entry>
	<entry>
		<id>https://wiki.algo.informatik.tu-darmstadt.de/index.php?title=Array_list:_find&amp;diff=2875&amp;oldid=prev</id>
		<title>Weihe at 14:06, 16 May 2015</title>
		<link rel="alternate" type="text/html" href="https://wiki.algo.informatik.tu-darmstadt.de/index.php?title=Array_list:_find&amp;diff=2875&amp;oldid=prev"/>
		<updated>2015-05-16T14:06:19Z</updated>

		<summary type="html">&lt;p&gt;&lt;/p&gt;
&lt;table style=&quot;background-color: #fff; color: #202122;&quot; data-mw-interface=&quot;&quot;&gt;
				&lt;col class=&quot;diff-marker&quot; /&gt;
				&lt;col class=&quot;diff-content&quot; /&gt;
				&lt;col class=&quot;diff-marker&quot; /&gt;
				&lt;col class=&quot;diff-content&quot; /&gt;
				&lt;tr class=&quot;diff-title&quot; lang=&quot;en&quot;&gt;
				&lt;td colspan=&quot;2&quot; style=&quot;background-color: #fff; color: #202122; text-align: center;&quot;&gt;← Older revision&lt;/td&gt;
				&lt;td colspan=&quot;2&quot; style=&quot;background-color: #fff; color: #202122; text-align: center;&quot;&gt;Revision as of 14:06, 16 May 2015&lt;/td&gt;
				&lt;/tr&gt;&lt;tr&gt;&lt;td colspan=&quot;2&quot; class=&quot;diff-lineno&quot; id=&quot;mw-diff-left-l1&quot;&gt;Line 1:&lt;/td&gt;
&lt;td colspan=&quot;2&quot; class=&quot;diff-lineno&quot;&gt;Line 1:&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td class=&quot;diff-marker&quot; data-marker=&quot;−&quot;&gt;&lt;/td&gt;&lt;td style=&quot;color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;&#039;&#039;&#039;Algorithmic problem:&#039;&#039;&#039; [[&lt;del style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;Linear &lt;/del&gt;sequence: find]]&lt;/div&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot; data-marker=&quot;+&quot;&gt;&lt;/td&gt;&lt;td style=&quot;color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;&#039;&#039;&#039;Algorithmic problem:&#039;&#039;&#039; [[&lt;ins style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;Ordered sequence#Find|Ordered &lt;/ins&gt;sequence: find]]&lt;/div&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td class=&quot;diff-marker&quot;&gt;&lt;/td&gt;&lt;td style=&quot;background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;br&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot;&gt;&lt;/td&gt;&lt;td style=&quot;background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;br&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td class=&quot;diff-marker&quot;&gt;&lt;/td&gt;&lt;td style=&quot;background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;&amp;#039;&amp;#039;&amp;#039;Prerequisites:&amp;#039;&amp;#039;&amp;#039; None.&lt;/div&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot;&gt;&lt;/td&gt;&lt;td style=&quot;background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;&amp;#039;&amp;#039;&amp;#039;Prerequisites:&amp;#039;&amp;#039;&amp;#039; None.&lt;/div&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;/table&gt;</summary>
		<author><name>Weihe</name></author>
	</entry>
	<entry>
		<id>https://wiki.algo.informatik.tu-darmstadt.de/index.php?title=Array_list:_find&amp;diff=1965&amp;oldid=prev</id>
		<title>Pezi22 at 11:56, 10 November 2014</title>
		<link rel="alternate" type="text/html" href="https://wiki.algo.informatik.tu-darmstadt.de/index.php?title=Array_list:_find&amp;diff=1965&amp;oldid=prev"/>
		<updated>2014-11-10T11:56:24Z</updated>

		<summary type="html">&lt;p&gt;&lt;/p&gt;
&lt;table style=&quot;background-color: #fff; color: #202122;&quot; data-mw-interface=&quot;&quot;&gt;
				&lt;col class=&quot;diff-marker&quot; /&gt;
				&lt;col class=&quot;diff-content&quot; /&gt;
				&lt;col class=&quot;diff-marker&quot; /&gt;
				&lt;col class=&quot;diff-content&quot; /&gt;
				&lt;tr class=&quot;diff-title&quot; lang=&quot;en&quot;&gt;
				&lt;td colspan=&quot;2&quot; style=&quot;background-color: #fff; color: #202122; text-align: center;&quot;&gt;← Older revision&lt;/td&gt;
				&lt;td colspan=&quot;2&quot; style=&quot;background-color: #fff; color: #202122; text-align: center;&quot;&gt;Revision as of 11:56, 10 November 2014&lt;/td&gt;
				&lt;/tr&gt;&lt;tr&gt;&lt;td colspan=&quot;2&quot; class=&quot;diff-lineno&quot; id=&quot;mw-diff-left-l5&quot;&gt;Line 5:&lt;/td&gt;
&lt;td colspan=&quot;2&quot; class=&quot;diff-lineno&quot;&gt;Line 5:&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td class=&quot;diff-marker&quot;&gt;&lt;/td&gt;&lt;td style=&quot;background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;&amp;#039;&amp;#039;&amp;#039;Type of algorithm:&amp;#039;&amp;#039;&amp;#039; loop&lt;/div&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot;&gt;&lt;/td&gt;&lt;td style=&quot;background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;&amp;#039;&amp;#039;&amp;#039;Type of algorithm:&amp;#039;&amp;#039;&amp;#039; loop&lt;/div&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td class=&quot;diff-marker&quot;&gt;&lt;/td&gt;&lt;td style=&quot;background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;br&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot;&gt;&lt;/td&gt;&lt;td style=&quot;background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;br&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td class=&quot;diff-marker&quot; data-marker=&quot;−&quot;&gt;&lt;/td&gt;&lt;td style=&quot;color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;&#039;&#039;&#039;Auxiliary data:&#039;&#039;&#039; A pointer &amp;lt;math&amp;gt;p&amp;lt;/math&amp;gt; of type &quot;pointer to list item of array lists of &lt;del style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;compnent &lt;/del&gt;type &amp;lt;math&amp;gt;\Kappa&amp;lt;/math&amp;gt;&quot;.&lt;/div&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot; data-marker=&quot;+&quot;&gt;&lt;/td&gt;&lt;td style=&quot;color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;&#039;&#039;&#039;Auxiliary data:&#039;&#039;&#039; A pointer &amp;lt;math&amp;gt;p&amp;lt;/math&amp;gt; of type &quot;pointer to list item of array lists of &lt;ins style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;component &lt;/ins&gt;type &amp;lt;math&amp;gt;\Kappa&amp;lt;/math&amp;gt;&quot;.&lt;/div&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td class=&quot;diff-marker&quot;&gt;&lt;/td&gt;&lt;td style=&quot;background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;br&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot;&gt;&lt;/td&gt;&lt;td style=&quot;background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;br&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td class=&quot;diff-marker&quot;&gt;&lt;/td&gt;&lt;td style=&quot;background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;== Abstract view ==&lt;/div&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot;&gt;&lt;/td&gt;&lt;td style=&quot;background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;== Abstract view ==&lt;/div&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;/table&gt;</summary>
		<author><name>Pezi22</name></author>
	</entry>
	<entry>
		<id>https://wiki.algo.informatik.tu-darmstadt.de/index.php?title=Array_list:_find&amp;diff=1210&amp;oldid=prev</id>
		<title>Dkratschmann: Created page with &quot;&#039;&#039;&#039;Algorithmic problem:&#039;&#039;&#039; Linear sequence: find  &#039;&#039;&#039;Prerequisites:&#039;&#039;&#039; None.  &#039;&#039;&#039;Type of algorithm:&#039;&#039;&#039; loop  &#039;&#039;&#039;Auxiliary data:&#039;&#039;&#039; A pointer &lt;math&gt;p&lt;/math&gt; of type &quot;pointe...&quot;</title>
		<link rel="alternate" type="text/html" href="https://wiki.algo.informatik.tu-darmstadt.de/index.php?title=Array_list:_find&amp;diff=1210&amp;oldid=prev"/>
		<updated>2014-10-14T18:36:29Z</updated>

		<summary type="html">&lt;p&gt;Created page with &amp;quot;&amp;#039;&amp;#039;&amp;#039;Algorithmic problem:&amp;#039;&amp;#039;&amp;#039; &lt;a href=&quot;/index.php?title=Linear_sequence:_find&amp;amp;action=edit&amp;amp;redlink=1&quot; class=&quot;new&quot; title=&quot;Linear sequence: find (page does not exist)&quot;&gt;Linear sequence: find&lt;/a&gt;  &amp;#039;&amp;#039;&amp;#039;Prerequisites:&amp;#039;&amp;#039;&amp;#039; None.  &amp;#039;&amp;#039;&amp;#039;Type of algorithm:&amp;#039;&amp;#039;&amp;#039; loop  &amp;#039;&amp;#039;&amp;#039;Auxiliary data:&amp;#039;&amp;#039;&amp;#039; A pointer &amp;lt;math&amp;gt;p&amp;lt;/math&amp;gt; of type &amp;quot;pointe...&amp;quot;&lt;/p&gt;
&lt;p&gt;&lt;b&gt;New page&lt;/b&gt;&lt;/p&gt;&lt;div&gt;&amp;#039;&amp;#039;&amp;#039;Algorithmic problem:&amp;#039;&amp;#039;&amp;#039; [[Linear sequence: find]]&lt;br /&gt;
&lt;br /&gt;
&amp;#039;&amp;#039;&amp;#039;Prerequisites:&amp;#039;&amp;#039;&amp;#039; None.&lt;br /&gt;
&lt;br /&gt;
&amp;#039;&amp;#039;&amp;#039;Type of algorithm:&amp;#039;&amp;#039;&amp;#039; loop&lt;br /&gt;
&lt;br /&gt;
&amp;#039;&amp;#039;&amp;#039;Auxiliary data:&amp;#039;&amp;#039;&amp;#039; A pointer &amp;lt;math&amp;gt;p&amp;lt;/math&amp;gt; of type &amp;quot;pointer to list item of array lists of compnent type &amp;lt;math&amp;gt;\Kappa&amp;lt;/math&amp;gt;&amp;quot;.&lt;br /&gt;
&lt;br /&gt;
== Abstract view ==&lt;br /&gt;
&lt;br /&gt;
&amp;#039;&amp;#039;&amp;#039;Invariant:&amp;#039;&amp;#039;&amp;#039; After &amp;lt;math&amp;gt;i \ge 0&amp;lt;/math&amp;gt; iterations:&lt;br /&gt;
# The pointer &amp;lt;math&amp;gt;p&amp;lt;/math&amp;gt; points to the list item at position &amp;lt;math&amp;gt;i + 1&amp;lt;/math&amp;gt; (or is void if no such item exists).&lt;br /&gt;
# The first &amp;lt;math&amp;gt;i&amp;lt;/math&amp;gt; arrays in the list do not contain &amp;lt;math&amp;gt;\Kappa&amp;lt;/math&amp;gt;.&lt;br /&gt;
&lt;br /&gt;
&amp;#039;&amp;#039;&amp;#039;Variant:&amp;#039;&amp;#039;&amp;#039; The pointer &amp;lt;math&amp;gt;p&amp;lt;/math&amp;gt; is moved one step forward to the next array list item.&lt;br /&gt;
&lt;br /&gt;
&amp;#039;&amp;#039;&amp;#039;Break condition:&amp;#039;&amp;#039;&amp;#039; Either &amp;lt;math&amp;gt;p=&amp;lt;/math&amp;gt;void or, otherwise, &amp;lt;math&amp;gt;\Kappa \in \{p.A[1], \ldots, p.A[p.n]\}&amp;lt;/math&amp;gt;.&lt;br /&gt;
&lt;br /&gt;
== Induction basis == &lt;br /&gt;
&lt;br /&gt;
&amp;#039;&amp;#039;&amp;#039;Abstract view:&amp;#039;&amp;#039;&amp;#039; Set &amp;lt;math&amp;gt;p:=&amp;lt;/math&amp;gt; first.&lt;br /&gt;
&lt;br /&gt;
&amp;#039;&amp;#039;&amp;#039;Implementation:&amp;#039;&amp;#039;&amp;#039; Obvious.&lt;br /&gt;
&lt;br /&gt;
&amp;#039;&amp;#039;&amp;#039;Proof:&amp;#039;&amp;#039;&amp;#039; Nothing to show.&lt;br /&gt;
&lt;br /&gt;
== Induction step ==&lt;br /&gt;
&lt;br /&gt;
&amp;#039;&amp;#039;&amp;#039;Abstract view:&amp;#039;&amp;#039;&amp;#039;&lt;br /&gt;
# Terminate the algorithm if the end of the list is reached or, otherwise, if &amp;lt;math&amp;gt;\Kappa&amp;lt;/math&amp;gt; is found in the current array.&lt;br /&gt;
# Otherwise, &amp;lt;math&amp;gt;p&amp;lt;/math&amp;gt; is moved one step forward to the next array.&lt;br /&gt;
&lt;br /&gt;
&amp;#039;&amp;#039;&amp;#039;Implementation:&amp;#039;&amp;#039;&amp;#039;&lt;br /&gt;
# If &amp;lt;math&amp;gt;p=&amp;lt;/math&amp;gt;void, terminate the algorithm and return &amp;lt;math&amp;gt;false&amp;lt;/math&amp;gt;.&lt;br /&gt;
# Otherwise, if &amp;lt;math&amp;gt;p.A[j] = \Kappa&amp;lt;/math&amp;gt; for some &amp;lt;math&amp;gt;j \in \{1, \ldots, p.n\}&amp;lt;/math&amp;gt;, set &amp;lt;math&amp;gt;p:=p.next&amp;lt;/math&amp;gt;.&lt;br /&gt;
&lt;br /&gt;
&amp;#039;&amp;#039;&amp;#039;Correctness:&amp;#039;&amp;#039;&amp;#039; Obvious.&lt;br /&gt;
&lt;br /&gt;
== Complexity ==&lt;br /&gt;
&lt;br /&gt;
&amp;#039;&amp;#039;&amp;#039;Statement:&amp;#039;&amp;#039;&amp;#039; Linear in the length of the sequence in the worst case.&lt;br /&gt;
&lt;br /&gt;
&amp;#039;&amp;#039;&amp;#039;Proff:&amp;#039;&amp;#039;&amp;#039; Obvious.&lt;/div&gt;</summary>
		<author><name>Dkratschmann</name></author>
	</entry>
</feed>