Slice a list of integers into four slices and applies bidirection search to each slices

Question

I am trying to write a function namely fourslicebidirectionSearch() where I have to do as a title said. My problem is I can write each function on its own but I couldn't figure out how to apply bidirection to four sliced integers.

def BiDirectionSearch(key, ls):
    i = 0  # to count a number loop
    j = len(ls) - 1
    while i < j:
        if ls[i] == key or ls[j] == key:
            return True, i + 1
        i += 1
        j -= 1
    return False, i


def FourSliceSearch(key, ls):
    n = int(len(ls) / 4)
    s1 = ls[0:n]
    s2 = ls[n:2 * n]
    s3 = ls[2 * n:3 * n]
    s4 = ls[3 * n:]
    i1 = 0
    i2 = 0
    i3 = 0
    i4 = 0
    count = 0  # to count a number of loop

    for i in range(len(s1)):

        if s1[i1] == key or s2[i2] == key or s3[i3] == key or s4[i4] == key:
            count += 1
            return True, count

        i1 += 1
        i2 += 1
        i3 += 1
        i4 += 1
        count += 1
    return False, count

myNum2 =  [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16]
key = 9

result, loopcount2 = BiDirectionSearch(key, myNum2)
result, loopcount3 = FourSliceSearch(key, myNum2)
if result:
    print(f'{key} is found in {myNum2}')
    print(f'For LienarSearch(), it takes {loopcount} loop(s) to find {key}.')
    print(f'For BiDirectionSearch(), it takes {loopcount2} loop(s) to find {key}.')
    print(f'For FourSliceSearch(), it takes {loopcount3} loop(s) to find {key}.')

else:
    print(f'{key} is not in {myNum2} and it takes {loopcount} loop(s)')

Answer 1

If you forgive my bad python skill I believe you are looking for something like this:

def FourWayBiSearch(key, ls):
    n = int(len(ls) / 4)
    parts = [ls[0:n], ls[n:2 * n], ls[2 * n:3 * n], ls[3 * n:]]
    loops = 0

    for part in parts
        found, index = BiDirectionSearch(key, part)
        loops += index
        if (found)
            return true, loops
    return false, loops

Note these are not run in parallel

Now was this what you were looking for?

The time complexity is the same for all 3 solutions O(N)

• its basically linear search O(N)
• If the numbers were sorted you could do a binary search in O(Log N)
• If they were sorted and uniformly distributed you can use interpolation search in O(log log N), note if the number are not uniformly distributed then its O(N) ... so be sure what you do.