TopCoder problem "BinarySearchable" used in SRM 281 (Division II Level Three)

Problem Statement


Binary search is a search algorithm usually used on a sorted sequence to quickly find an element with a given value. The algorithm works by repeatedly comparing the sought value with some element from the sequence (the pivot), then discarding as much of the sequence as possible based on the comparison and the assumption that the sequence is sorted. Note that in the standard algorithm, the pivot element is as close as possible to the middle of the sequence, but we'll remove that restriction.

The pseudocode for performing binary search on a sequence S, looking for value X is as follows:

  1 binary_search(S, X)
  2    while S is not empty
  3       choose an element from S as the pivot

  4       if pivot = X, return true (X was found)
  5       else if pivot < X, remove pivot and all elements before it from S
  6       else remove pivot and all elements after it from S
  7    end while
  8    return false (X was not found)

In this problem we will evaluate how binary search performs on data that isn't necessarily sorted. An element of S is said to be binary searchable if, regardless of how the pivot is chosen on line 3 whenever the line is executed, the above algorithm returns true.

Given a int[] sequence containing distinct integers, return the number of elements from the sequence that are binary searchable.



Method signature:int howMany(int[] sequence)
(be sure your method is public)


-sequence will contain between 0 and 50 elements, inclusive.
-Each element in sequence will be between -10000 and 10000, inclusive.
-sequence will contain no duplicates.


{ 1, 3, 2 }
Returns: 1
However we choose the pivots in the algorithm, we will always find the number 1 when looking for it. This does not hold for 3 and 2.
{ 3, 2, 1, 10, 23, 22, 21 }
Returns: 1
{ 1, 5, 7, 11, 12, 18 }
Returns: 6
All elements in a sorted sequence are binary searchable.
{ 5, 4, 3, 2, 1, 0 }
Returns: 0
{ 1, 3, 2, 4, 5, 7, 6, 8 }
Returns: 4

Problem url:

Problem stats url:




PabloGilberto , brett1479 , Olexiy

Problem categories:

Dynamic Programming, Search