binary_search

Sorting and searching16

Objective

Implement a function that locates key in an increasing sequence you can only read one element at a time through the callback at, spending at most 24 reads.

Steps

There is no array. at(i) hands you the value stored at index i, and it is the only way to see the sequence. Grademe counts every call, so each one costs you something.
The sequence holds n values and is already sorted in non-decreasing order: at(0) <= at(1) <= ... <= at(n - 1). Take that as given, never check it.
Call at only with an index inside [0, n). An index of n or beyond is an out of range read even when it looks harmless.
Return the index of key as a long. The same value may appear several times in a row, and the answer is the smallest index holding it, never a later one.
An n of 0 means there is nothing to look at. Return before calling at a single time.
Budget: 24 calls to at per search, for any n up to 1000000. Walking the indices from 0 upward answers every short sequence and then burns half a million reads on a long one. Discard half of what is left on each read instead.
Grademe prints the value you returned next to what the search cost: idx=3 probes<=24 when the call stayed inside the budget. Go over it and the real count is printed instead, as in probes=1000000. Read outside [0, n) and it prints probes=out-of-range.
Return -1 when no index holds key. A key below at(0), a key above at(n - 1), and a key that falls between two neighbours all end the same way.

examples

$ binary_search(7, 8, at) over {2, 4, 6, 8, 10, 12, 14}

idx=3 probes<=24

$ binary_search(5, 3, at) over {1, 3, 3, 3, 5}

idx=1 probes<=24

$ binary_search(7, 9, at) over {2, 4, 6, 8, 10, 12, 14}

idx=-1 probes<=24

$ binary_search(1000000, 1999998, at) with at(i) = i * 2

idx=999999 probes<=24

$ the same call, answered by reading index 0, then 1, then 2, and so on

idx=999999 probes=1000000

Constraints

Expected files

binary_search.c

Allowed functions

None. Write every helper yourself.

Allowed headers

<stddef.h>defines size_t

Tests

Run the tests to grade your code

Build

01Key sitting in the middle

02Key at index zero

03Key at the last index

04Key missing from the middle

05Key smaller than the first value

06Key larger than the last value

07n of zero probes nothing

08One element holding the key

09One element, wrong value

10Two elements, lower one

11Two elements, upper one

12A run of duplicates returns its first index

13Every value is the key

14Duplicates sit before the key

15Negative values and a duplicated key

16Even length, key near the tail

17Even length, key missing

18The smallest int as the key

19The largest int as the key

20Values past index n - 1 are out of reach

21A million elements, key at index zero

22A million elements, key at the last index

23A million elements, no odd value to find

24A million elements, key past the end

25600000 duplicates before the key

26600000 copies of the key, first index wins

27Two distinct values, neither is the key

binary_search

Objective

Implement a function that locates key in an increasing sequence you can only read one element at a time through the callback at, spending at most 24 reads.

Steps

There is no array. at(i) hands you the value stored at index i, and it is the only way to see the sequence. Grademe counts every call, so each one costs you something.
The sequence holds n values and is already sorted in non-decreasing order: at(0) <= at(1) <= ... <= at(n - 1). Take that as given, never check it.
Call at only with an index inside [0, n). An index of n or beyond is an out of range read even when it looks harmless.
Return the index of key as a long. The same value may appear several times in a row, and the answer is the smallest index holding it, never a later one.
An n of 0 means there is nothing to look at. Return before calling at a single time.
Budget: 24 calls to at per search, for any n up to 1000000. Walking the indices from 0 upward answers every short sequence and then burns half a million reads on a long one. Discard half of what is left on each read instead.
Grademe prints the value you returned next to what the search cost: idx=3 probes<=24 when the call stayed inside the budget. Go over it and the real count is printed instead, as in probes=1000000. Read outside [0, n) and it prints probes=out-of-range.
Return -1 when no index holds key. A key below at(0), a key above at(n - 1), and a key that falls between two neighbours all end the same way.

examples

$ binary_search(7, 8, at) over {2, 4, 6, 8, 10, 12, 14}

idx=3 probes<=24

$ binary_search(5, 3, at) over {1, 3, 3, 3, 5}

idx=1 probes<=24

$ binary_search(7, 9, at) over {2, 4, 6, 8, 10, 12, 14}

idx=-1 probes<=24

$ binary_search(1000000, 1999998, at) with at(i) = i * 2

idx=999999 probes<=24

$ the same call, answered by reading index 0, then 1, then 2, and so on

idx=999999 probes=1000000

Constraints

Expected files

binary_search.c

Allowed functions

None. Write every helper yourself.

Allowed headers

<stddef.h>defines size_t

binary_search

Sorting and searching16

Objective

Implement a function that locates key in an increasing sequence you can only read one element at a time through the callback at, spending at most 24 reads.

Steps

There is no array. at(i) hands you the value stored at index i, and it is the only way to see the sequence. Grademe counts every call, so each one costs you something.
The sequence holds n values and is already sorted in non-decreasing order: at(0) <= at(1) <= ... <= at(n - 1). Take that as given, never check it.
Call at only with an index inside [0, n). An index of n or beyond is an out of range read even when it looks harmless.
Return the index of key as a long. The same value may appear several times in a row, and the answer is the smallest index holding it, never a later one.
An n of 0 means there is nothing to look at. Return before calling at a single time.
Budget: 24 calls to at per search, for any n up to 1000000. Walking the indices from 0 upward answers every short sequence and then burns half a million reads on a long one. Discard half of what is left on each read instead.
Grademe prints the value you returned next to what the search cost: idx=3 probes<=24 when the call stayed inside the budget. Go over it and the real count is printed instead, as in probes=1000000. Read outside [0, n) and it prints probes=out-of-range.
Return -1 when no index holds key. A key below at(0), a key above at(n - 1), and a key that falls between two neighbours all end the same way.

examples

$ binary_search(7, 8, at) over {2, 4, 6, 8, 10, 12, 14}

idx=3 probes<=24

$ binary_search(5, 3, at) over {1, 3, 3, 3, 5}

idx=1 probes<=24

$ binary_search(7, 9, at) over {2, 4, 6, 8, 10, 12, 14}

idx=-1 probes<=24

$ binary_search(1000000, 1999998, at) with at(i) = i * 2

idx=999999 probes<=24

$ the same call, answered by reading index 0, then 1, then 2, and so on

idx=999999 probes=1000000

Constraints

Expected files

binary_search.c

Allowed functions

None. Write every helper yourself.

Allowed headers

<stddef.h>defines size_t

Tests

Run the tests to grade your code

Build

01Key sitting in the middle

02Key at index zero

03Key at the last index

04Key missing from the middle

05Key smaller than the first value

06Key larger than the last value

07n of zero probes nothing

08One element holding the key

09One element, wrong value

10Two elements, lower one

11Two elements, upper one

12A run of duplicates returns its first index

13Every value is the key

14Duplicates sit before the key

15Negative values and a duplicated key

16Even length, key near the tail

17Even length, key missing

18The smallest int as the key

19The largest int as the key

20Values past index n - 1 are out of reach

21A million elements, key at index zero

22A million elements, key at the last index

23A million elements, no odd value to find

24A million elements, key past the end

25600000 duplicates before the key

26600000 copies of the key, first index wins

27Two distinct values, neither is the key