Finding an element in a sorted array: Difference between revisions
Jump to navigation
Jump to search
(→Input) |
(→Input) |
||
| Line 1: | Line 1: | ||
== Input == | == Input == | ||
# An array <math>A</math> of some component type <math>S</math> | # An array <math>A</math> of some component type <math>S</math>. | ||
# A definition of [[Genericity#Comparison|comparison]] on <math>S</math> | # A definition of [[Genericity#Comparison|comparison]] on <math>S</math>. | ||
# An element <math>s\in S</math>. | |||
'''Prerequisite''': The components of <math>A</math> are sorted in ascending order according to the comparison. | '''Prerequisite''': The components of <math>A</math> are sorted in ascending order according to the comparison. | ||
== Output == | == Output == | ||
If <math>s</math> equals at least one of the components of <math>A</math>, the index of one of the occurrences is returned; otherwise, the information is returned that <math>s</math> is ''not'' in <math>A</math>. | If <math>s</math> equals at least one of the components of <math>A</math>, the index of one of the occurrences is returned; otherwise, the information is returned that <math>s</math> is ''not'' in <math>A</math>. | ||
Latest revision as of 05:52, 27 April 2016
Input
- An array [math]\displaystyle{ A }[/math] of some component type [math]\displaystyle{ S }[/math].
- A definition of comparison on [math]\displaystyle{ S }[/math].
- An element [math]\displaystyle{ s\in S }[/math].
Prerequisite: The components of [math]\displaystyle{ A }[/math] are sorted in ascending order according to the comparison.
Output
If [math]\displaystyle{ s }[/math] equals at least one of the components of [math]\displaystyle{ A }[/math], the index of one of the occurrences is returned; otherwise, the information is returned that [math]\displaystyle{ s }[/math] is not in [math]\displaystyle{ A }[/math].