1. Engineering
  2. Computer Science
  3. the issue i am having is over the whole quotspaceship...

Question: the issue i am having is over the whole quotspaceship...

Question details

The issue I am having is over the whole "spaceship operator" thing. Not sure if we're allowed to use Binary Search or not.

Suppose that we are given a sorted array A[1..n] of n numbers. Our goal is to determine whether or not the array A contains duplicate elements. We will limit ourselves to algorithms that use only the spaceship operator for comparisons, where

a <=> b := if

a < b then return -1

if a = b then return 0

if a > b then return 1

if a and b are not comparable then return nil

No other methods will be used to compare or inspect elements of the array.

(a) Give an efficient (optimal) comparison-based algorithm that decides whether A[1..n] contains duplicates using the spaceship operator for comparisons.

(b) Use an adversarial argument to show that no algorithm can solve the problem with fewer calls to the comparison operator than the algorithm that you gave in (a).

Solution by an expert tutor
Blurred Solution
This question has been solved
Subscribe to see this solution