CODEWITHSUNDEEP
python
Arjun
Arjun

Reputation: 907

Incorrect output for Binary Search with strings

I have a typical Binary Search algorithm implementation: 

def binarySearch(arr, element):
    first = 0
    last = len(arr) - 1
    while first <= last:
        i = (first + last) // 2
        if arr[i] == element:
            return 'Found at position: {}'.format(i)
        elif arr[i] > element:
            last = i - 1
        elif arr[i] < element:
            first = i + 1

The test data is as follows: 

arr = ['0006', '000e', '000f', '0023', '002a', '002E1627', '0032A542', '0037']

When I make a call to the binarySearch() function as follows:

element = '002E1627'
print (binarySearch(arr, element))

I get the output as: 

Found at position: 5

However, with the following input: 

element = '002a'
print (binarySearch(arr, element))

I get the output as: 

None

What is the reason behind this output?

The expected output for the second case is: Found at position: 4.

Upvotes: 0

Views: 90

Answers (2)

ShpielMeister
ShpielMeister

Reputation: 1455

just convert to a single case:

def binarySearch(arr, element):
    first = 0
    last = len(arr) - 1
    while first <= last:
        i = (first + last) // 2
        if arr[i].upper() == element.upper():
            return 'Found at position: {}'.format(i)
        elif arr[i].upper() > element.upper():
            last = i - 1
        elif arr[i].upper() < element.upper():
            first = i + 1

element = '002a'
print (binarySearch(arr, element))

Found at position: 4

Upvotes: 1

Zionsof
Zionsof

Reputation: 1246

The problem is that binary search works only with sorted arrays/lists.

Since the character a comes after the character E (Lower case are always after uppercase letters), then your list isn't sorted at all.

The list should be:

arr = ['0006', '000e', '000f', '0023', '002E1627', '002a', '0032A542', '0037']

Then you'll get your desired output

Upvotes: 1

Related Questions