Skip to content

Instantly share code, notes, and snippets.

@loisgh
Created February 23, 2018 21:39
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save loisgh/50e32ccc87e3a5b393bfec0461769da5 to your computer and use it in GitHub Desktop.
Save loisgh/50e32ccc87e3a5b393bfec0461769da5 to your computer and use it in GitHub Desktop.
def find_1d_peak(the_list, first, last):
if first == last:
return first
if last == first + 1 and the_list[first] >= the_list[last]:
return first
if last == first + 1 and the_list[first] < the_list[last]:
return last
mid = (first + last )//2
if the_list[mid] > the_list[mid + 1] and the_list[mid] > the_list[mid - 1]:
return mid
if the_list[mid] > the_list[mid + 1] and the_list[mid] < the_list[mid - 1]:
return find_1d_peak(the_list, first, mid -1)
else:
return find_1d_peak(the_list, mid + 1, last)
def find_2d_peak(pm, first, last):
mid = first - (last + first) / 2
row = mid
col = find_1d_peak(pm[row], 0, len(pm[row]))
if pm[row][col] > pm[row+1][col] and pm[row][col] > pm[row-1][col]:
return (pm[row][col], row, col)
elif pm[row][col] > pm[row+1][col] and pm[row][col] < pm[row-1][col]:
return find_2d_peak(pm, first, row-1)
else:
return find_2d_peak(pm, row+1, last)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment