Find maximum element in bitonic array An array is bitonic if it is composed of an increasing sequence of integers followed immediately by a decreasing sequence of integers. Write a program that, given a bitonic array of N distinct integer values, determines whether a given integer is in the array.


I have divided the problem in two sub-problems:


Find the maximum.
Do the binary search on left and right half.


Here is the complete solution:

def bin_search(ary, elem, low, high):
    """ Search element in array of ascending order."""
    # Gaurd clause, if element is not in array,
    if low &gt; high:
        return None
    mid = low + (high - low) / 2
    if (ary[mid] &lt; elem):
        return bin_search(ary, elem, mid + 1, high)
    elif (ary[mid] &gt; elem):
        return bin_search(ary, elem, low, mid - 1)
    else:
        return mid

def bin_search_reverse(ary, elem, low, high):
    """ Search element in array of descending order."""
    # Gaurd clause, if element is not in array,
    if low &gt; high:
        return None
    mid = low + (high - low) / 2
    if (ary[mid] &gt; elem):
        return bin_search_reverse(ary, elem, mid + 1, high)
    elif (ary[mid] &lt; elem):
        return bin_search_reverse(ary, elem, low, mid - 1)
    else:
        return mid

def find_max_bitonic(ary):
    def recurse(low, high):
        mid = low + (high - low) / 2
        # Handle base cases first.
        if (high - low == 1):
            return high

        if (ary[mid] &lt; ary[mid+1]):
            return recurse(mid, high) # Go right.
        else:
            return recurse(low, mid)
    return recurse(0, len(ary) - 1)

def search(ary, elem):
    maximum = find_max_bitonic(ary)
    if (ary[maximum] == elem):
        return maximum
    left = bin_search(ary, elem, 0, maximum - 1)
    right = bin_search_reverse(ary, elem, maximum + 1, len(ary) - 1)
    return left or right


ary = (5, 15, 25, 35, 40, 45, 20, 10, 2)
print search(ary, 20)


I think there is a scope of lot of improvements. I personally think writing two separate methods for binary search can be avoided but don't know if there is any elegant alternative.

Running time

\$log_{2}O(N)\$(Finding maximum) + 2\$log_{2}O(N)\$(Binary search) = \$3log_{2}O(N)\$
Some comments based on my first impression:


Your code is a bit sparse on comments or documentation. Some more of that would be nice, in particular explain what arguments I’m supposed to supply to functions, and how I should interpret the return values.
Don’t skimp on characters for variable names. ary ~> array, elem ~> element. More expressive variable names are better; there's no need not to use full words.
The problem states “determine whether a given integer is in the array”, which sounds like a boolean. As such, I expected your search() function to return True/False.

Instead it returns a number (the index of the element if present) or None. That’s not wrong, but a docstring would have been helpful there.


On to more substantive comments:


You can definitely reduce the amount of code duplication in the two binary search functions.

Right now the binary search functions are responsible for picking the subset of the array that they search. I think that would be better handled by the caller – they should choose which subset of the array to inspect. That allows you to tidy up the search:

def binary_search(array, element):
    """Given an array of elements sorted in ascending order,
    perform a binary search to find this element.
    """
    ...


and then when you want to do a search in descending order, you can reverse the array before passing it in. Alternatively, you could do a check for the direction of the array when it’s passed into this function, and reverse it if necessary.

Then in your search function, take slices of the array and pass it into this function.
You can speed up some cases with a simple bounds check on the two halves of the array. Check that the element is between the first and last elements of the array.

For example: if I have a sorted array of 100 elements [1, ..., 1000], I know that –5 isn’t in that array just by inspecting the first and last numbers, without doing a binary search.

Adding a check that a number could plausibly be in an array will save you some operations.
In the search function, you check both the left and right-hand arrays before returning a result. If you find the element in the left-hand array, the result won’t change based on the right-hand array, so checking it is wasting CPU cycles.

A better approach would be something like:

if bin_search(ary, elem, 0, maximum - 1):  # left-hand array
    return True
elif bin_search_reverse(ary, elem, maximum + 1, len(ary) - 1)  # right-hand
    return True
else:
    return False


This is called short-circuit evaluation. You might be able to fit it onto one line – the or statement does this automatically – but the example above illustrates the principle.