Using Python implement the binary search below without using recursion, without

Question

Using Python implement the binary search below without using recursion, without the slice operator or any other lists other than the original list. You will need to pass the list along with the starting and ending index values for the sublist.

The definition of binary search will then just be:

def binarySearch( x, list )
Here is the pseudo code for the binarySearch ( make sure to read NOTE below):

NOTE:

The pseudo code above is written for arrays that start at index 1 and the last element of the array is index of n, lists in python start at 0 and end at n-1.

-You must change the implementation of the algorithm above to use python lists that start at 0 and also return    the index of the array where the item is found, and -1 if not found.

In the pseudo code above: = indicates assignment, single = indicates test if equal, the [X>A[mid]] in the else part is a comment. but sometimes the [ ] group a expression like ( ) as in the mid := [ statement

You should write your own test of the binary search, I will use my own to test various sorted lists of yours will correctly return the index -1 if found.

HERE IS A SAMPLE TEST:

a =[ 10,30,31,44,60,81,90,101,102,103] # this is sorted

assert   binarySearch(31,a) == 2, "check if found 31 at 2"

assert binarySearch(91,a) == -1, "check 91 not found returns -1"

assert binarySearch(200,a) == -1, "check 200 not found returns -1"

a =[ 10,30,31,44,60,81,90,101,102,103]

assert binarySearch(31,a) == 2, "check if found 31 at 2"

assert binarySearch(91,a) == -1, "check 91 not found returns -1"

assert binarySearch(200,a) == -1, "check 200 not found returns -1"

a = [ 'able', "cane", 'joe', 'mary', 'nancy', 'xee' ]

assert binarySearch('abe',a) == -1, "abe should return -1"

assert binarySearch('mary',a) == 3, "mary should return 3"

print("ALL PASSED")

NOTE:

The pseudo code above is written for arrays that start at index 1 and the last element of the array is index of n, lists in python start at 0 and end at n-1.

-You must change the implementation of the algorithm above to use python lists that start at 0 and also return    the index of the array where the item is found, and -1 if not found.

In the pseudo code above: = indicates assignment, single = indicates test if equal, the [X>A[mid]] in the else part is a comment. but sometimes the [ ] group a expression like ( ) as in the mid := [ statement

Explanation / Answer

__author__ = 'praveenkotekal'

def binarySearch(element_to_be_searched,listofelements):
'''
:param listofelements:
:param element_to_be_searched:
:return index if found else return -1
'''
low = 0
high = len(listofelements)-1
while low <=high:
mid = (low + high)/2
if a[mid]==element_to_be_searched:
return mid
elif a[mid]<element_to_be_searched:
low = mid + 1
else:
high = mid -1
return -1

a =[ 10,30,31,44,60,81,90,101,102,103] # this is sorted

print binarySearch(31,a) == 2, "check if found 31 at 2"

print binarySearch(91,a) == -1, "check 91 not found returns -1"

print binarySearch(200,a) == -1, "check 200 not found returns -1"

a =[ 10,30,31,44,60,81,90,101,102,103]

print binarySearch(31,a) == 2, "check if found 31 at 2"

print binarySearch(91,a) == -1, "check 91 not found returns -1"

print binarySearch(200,a) == -1, "check 200 not found returns -1"

a = [ 'able', "cane", 'joe', 'mary', 'nancy', 'xee' ]

print binarySearch('abe',a) == -1, "abe should return -1"

print binarySearch('mary',a) == 3, "mary should return 3"

print("ALL PASSED")

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.