1D Peak Finding Algorithm in Python using Divide and Conquer

Question

I am trying to implement an 1D peak algorithm in python, though I am having troubles implementing it. The idea is that it compares the central term of the array and picks the side with the higher neighbour term. That half becomes the new array. Only when the central is the largest term, does it become the peak. Here is my code: import math

import math

array = [1,2,3,4,5,6,7]
size = len(array)
count = 0

while count == 0: 
    if len(array) == 2:
        count += 1
        print(max(array[0],array[1])) 
        break
    elif count == 0: 
        elif array[math.floor(abs(size/2))] < array[math.floor(abs(size/2))-1]:
            new_array = [] 
            for i in range(int(abs(size)/2)):
                new_array.append(array[i])
                array = new_array
        elif array[math.floor(abs(size/2))] < array[math.floor(abs(size/2))+1]:
            new_array = []
            for j in range(math.floor(abs(size)/2),size): 
                new_array.append(array[j])
            array = new_array
        elif count == 0: 
            count += 1
            print(array[math.floor(abs(size/2))])
            break

I keep on getting errors, and I can not seem to identify the problem. Can anyone help out?

aeternalis1 · Accepted Answer · 2020-03-29 15:21:59Z

1

Another problem (aside from compuphy's catch) is the fact that you don't change your variable "size" upon resizing your array, which is liable to lead to IndexErrors. Also, a few nitpicks:

There's no point in doing abs(size/2), since it'll always be positive.
Instead of floor(size/2), if this is python 3, just do size//2 for integer division, or if it's python 2, just size/2 will suffice.
The way your program is implemented makes the runtime greater than O(logN), which I assume you're targeting, so I think you should look into implementations where you keep an upper and lower bound of the subarray you're searching rather than making a new array in every iteration.

answered Mar 29, 2020 at 15:21

aeternalis1

6754 silver badges7 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

compuphys · Accepted Answer · 2020-03-29 15:16:15Z

0

You have elif's in the first elif condition but without any preceeding if's:

elif count == 0: 
        elif array[math.floor(abs(size/2))] < array[math.floor(abs(size/2))-1]:
        ^^^^

try changing those to if

answered Mar 29, 2020 at 15:16

compuphys

1,37714 silver badges29 bronze badges

2 Comments

Dr. Ernesto Chinchilla Over a year ago

I tried that, which fixes one problem, but the followinf error keeps coming up:

Dr. Ernesto Chinchilla Over a year ago

Traceback (most recent call last): File "PeakFinder1D.py", line 21, in <module> elif array[math.floor(abs(size/2))] < array[math.floor(abs(size/2))+1]: IndexError: list index out of range

Collectives™ on Stack Overflow

1D Peak Finding Algorithm in Python using Divide and Conquer

2 Answers 2

Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related