#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Mon Feb 27 23:54:08 2017

@author: coskun

Exercise: is in
5/5 points (graded)
ESTIMATED TIME TO COMPLETE: 18 minutes

We can use the idea of bisection search to determine if a character 
is in a string, so long as the string is sorted in alphabetical order.

First, test the middle character of a string against the character 
you're looking for (the "test character"). If they are the same, 
we are done - we've found the character we're looking for!

If they're not the same, check if the test character is "smaller" than 
the middle character. If so, we need only consider the lower half of 
the string; otherwise, we only consider the upper half of the string. 
(Note that you can compare characters using Python's < function.)

Implement the function isIn(char, aStr) which implements the above idea 
recursively to test if char is in aStr. 'char' will be a single character 
and 'aStr' will be a string that is in alphabetical order. 
The function should return a boolean value.

As you design the function, think very carefully about 
what the base cases should be.
"""

#This is my test case
aStr='abcdefghijklmnopqrstuvwxyz'

def isIn(char, aStr):
    '''
    char: a single character
    aStr: an alphabetized string
    
    returns: True if char is in aStr; False otherwise
    '''
    # Safety Belt
    if aStr == '' or char == '':
        return False
    
    # Your code here
    g=len(aStr)//2
    # Set Base 1  -- a Fix for subdivistion falls to zero in the end.
    if g == 0:
        if char == aStr[g]:
            return True
        else:
            return False
    # Set Base 2
    if char == aStr[g]:
        return True
    else:
        if char < aStr[g]:
            #Go left
            return isIn(char, aStr[0:g])
        elif char > aStr[g]:
            #Go right
            return isIn(char, aStr[g:])

print(isIn("l", aStr))