Dichotomic search P81966


Statement
 

pdf   zip   main.cc   main.c   main.java   main.py

thehtml

Write an efficient recursive function that returns the position of @x@ in the subvector @v@[@left@..@right@]. The function must return −1 if @x@ does not belong to @v@[@left@..@right@] or if @left@ > @right@.

Precondition

The vector @v@ is sorted in strictly increasing order. Moreover, we have 0 ≤ @left@ ≤ size of v and −1 ≤ @right@ < size of v.

Interface

C++
int position(double x, const vector<double>& v, int left, int right);
C
int position(double x, double v[], int left, int right);
Java
public static int position(double x, double[] v, int left, int right);
Python
position(x, v, left, right) # returns int
MyPy
position(x: float, v: list[float], left: int, right: int) -> int

Observation You only need to submit the required procedure; your main program will be ignored.

Information
Author
Salvador Roura
Language
English
Translator
Carlos Molina
Original language
Catalan
Other languages
Catalan
Official solutions
C C++ Java Python
User solutions
C C++ Java Python