DIvide & conquer Flashcards
Merge sort algorithm
Merge sort is an efficient sorting algorithm that produces a stable sort, which means that if two elements have the same value, they hold the same relative position in the sorted sequence as they did in the input. In other words, the relative order of elements with equal values is preserved in the sorted sequence. Merge sort is a comparison sort, which means that it can sort any input for which a less-than relation is defined.
worst-case time complexity of merge sort is O(n.log(n)), where n is the size of the input.
def mergeSort(A):
if len(A)>1:
mid = len(A)//2
L = A[:mid]
R = A[mid:]
i=j=k = 0
mergeSort(L)
mergeSort(R)
while i< len(L) and j< len(R):
if L[i] < R[j]:
A[k] = L[i]
i += 1
else:
A[k] = R[j]
j += 1
k+=1
while i < len(L):
A[k] = L[i]
i += 1
k+=1
while j< len(R):
A[k] = R[j]
j+=1
k+=1
return A A = [12, 3, 18, 24, 0, 5, -2] mergeSort(A)
______________- Second approcah___________
2 functions and copy of the array:
def merge –>Merge two sorted sublists A[low … mid] and `A[mid+1 … high]
def mergesort --> call itself on low, mid and mid+1, high then use the merge function to connect two halves.
# Merge two sorted sublists `A[low … mid]` and `A[mid+1 … high]` def merge(A, aux, low, mid, high):
k = low i = low j = mid + 1
# While there are elements in the left and right runs
while i <= mid and j <= high:
if A[i] <= A[j]:
aux[k] = A[i]
k = k + 1
i = i + 1
else:
aux[k] = A[j]
k = k + 1
j = j + 1
# Copy remaining elements
while i <= mid:
aux[k] = A[i]
k = k + 1
i = i + 1
# No need to copy the second half (since the remaining items
# are already in their correct position in the auxiliary array)
# copy back to the original list to reflect sorted order
for i in range(low, high + 1):
A[i] = aux[i]
# Sort list `A[low…high]` using auxiliary list aux def mergesort(A, aux, low, high):
# Base case
if high == low: # if run size == 1
return
# find midpoint
mid = (low + ((high - low) >> 1))
# recursively split runs into two halves until run size == 1,
# then merge them and return up the call chain
mergesort(A, aux, low, mid) # split/merge left half mergesort(A, aux, mid + 1, high) # split/merge right half merge(A, aux, low, mid, high) # merge the two half runs
# Function to check if `A` is sorted in ascending order or not def isSorted(A):
prev = A[0]
for i in range(1, len(A)):
if prev > A[i]:
print("MergeSort Fails!!")
return False
prev = A[i] return True
# Implementation of merge sort algorithm in Python if \_\_name\_\_ == '\_\_main\_\_':
A = [12, 3, 18, 24, 0, 5, -2] aux = A.copy()
# sort list `A` using auxiliary list `aux`
mergesort(A, aux, 0, len(A) - 1)
if isSorted(A):
print(A)
Quick sort
def swap(A, i, j):
temp = A[i] A[i] = A[j] A[j] = temp
# Partition using the Lomuto partition scheme def partition(a, start, end):
# Pick the rightmost element as a pivot from the list
pivot = a[end]
# elements less than the pivot will be pushed to the left of `pIndex`
# elements more than the pivot will be pushed to the right of `pIndex`
# equal elements can go either way
pIndex = start
# each time we find an element less than or equal to the pivot,
# `pIndex` is incremented, and that element would be placed
# before the pivot.
for i in range(start, end):
if a[i] <= pivot:
swap(a, i, pIndex)
pIndex = pIndex + 1
# swap `pIndex` with pivot
swap(a, end, pIndex)
# return `pIndex` (index of the pivot element)
return pIndex
# Quicksort routine def quicksort(a, start, end):
# base condition
if start >= end:
return
# rearrange elements across pivot
pivot = partition(a, start, end)
# recur on sublist containing elements less than the pivot
quicksort(a, start, pivot - 1)
# recur on sublist containing elements more than the pivot
quicksort(a, pivot + 1, end)
Find the frequency of each element in a sorted array containing duplicates
Given a sorted array containing duplicates, efficiently find each element’s frequency without traversing the whole array.
Input: [2, 2, 2, 4, 4, 4, 5, 5, 6, 8, 8, 9]
Output: {2: 3, 4: 3, 5: 2, 6: 1, 8: 2, 9: 1}
A simple solution would be to run a linear search on the array and count the number of occurrences of each element and finally print them. The problem with this approach is that its worst-case time complexity is O(n), where n is the input size, and we are scanning the whole array (violating problem constraints).
We can easily solve this problem in O(m.log(n)) time by taking advantage of the fact that the input is sorted and contains duplicates. Here m is the total number of distinct elements in the array, and n is the input size.
code iterative solution
# Function to find the frequency of each element in a sorted list def findFrequency(nums):
# dictionary to store the frequency of each element in the list
freq = {}
# search space is nums[left…right]
(left, right) = (0, len(nums) - 1)
# loop till the search space is exhausted
while left <= right:
# if nums[left…right] consists of only one element, update its count
if nums[left] == nums[right]:
freq[nums[left]] = freq.get(nums[left], 0) + (right - left + 1)
# now discard nums[left…right] and continue searching in
# nums[right+1… n-1] for nums[left]
left = right + 1
right = len(nums) - 1
else:
# reduce the search space
right = (left + right) // 2
return freq
recursive solution
# Function to find the frequency of each element in a sorted list def findFrequency(nums, left, right, freq):
if left > right:
return
# if every element in sublist nums[left…right] is equal,
# then increment the element's count by `n`
if nums[left] == nums[right]:
count = freq.get(nums[left])
if count is None:
count = 0
freq[nums[left]] = count + (right - left + 1)
return
mid = (left + right) // 2
# divide the list into left and right sublist and recur
findFrequency(nums, left, mid, freq)
findFrequency(nums, mid + 1, right, freq)
Find the minimum and maximum element in an array using Divide and Conquer
Given an integer array, find the minimum and maximum element present in it by making minimum comparisons by using the divide-and-conquer technique.
Input: nums = [5, 7, 2, 4, 9, 6]
Output:
The minimum array element is 2
The maximum array element is 9
import sys
# Divide and conquer solution to find the minimum and maximum number in a list def findMinAndMax(nums, left, right, min=sys.maxsize, max=-sys.maxsize):
# if the list contains only one element
if left == right: # common comparison
if min > nums[right]: # comparison 1
min = nums[right]
if max < nums[left]: # comparison 2
max = nums[left]
return min, max
# if the list contains only two elements
if right - left == 1: # common comparison
if nums[left] < nums[right]: # comparison 1
if min > nums[left]: # comparison 2
min = nums[left]
if max < nums[right]: # comparison 3
max = nums[right]
else:
if min > nums[right]: # comparison 2
min = nums[right]
if max < nums[left]: # comparison 3
max = nums[left]
return min, max
# find the middle element
mid = (left + right) // 2
# recur for the left sublist
min, max = findMinAndMax(nums, left, mid, min, max)
# recur for the right sublist
min, max = findMinAndMax(nums, mid + 1, right, min, max)
return min, max
Search an element in a circularly sorted array
Given a circularly sorted integer array, search an element in it. Assume there are no duplicates in the array, and the rotation is in the anti-clockwise direction.
Input:
nums = [8, 9, 10, 2, 5, 6] target = 10
Output: Element found at index 2
A simple solution would be to run a linear search on the array and find the given element’s index. The problem with this approach is that its worst-case time complexity is O(n), where n is the size of the input. This solution also does not take advantage of the fact that the input is circularly sorted.
We can easily solve this problem in O(log(n)) time by modifying the binary search algorithm. We know that the middle element always divides the array into two subarrays, and the target element can lie only in one of these subarrays. It is worth noticing that at least one of these subarrays will always be sorted. If the middle element happens to be the point of rotation (minimum element), then both left and right subarrays will be sorted, but in any case, one half (subarray) must be sorted. The idea is to use this property to discard the left half or the right half at each iteration of the binary search.
code
# Function to find an element in a circularly sorted list def searchCircularList(nums, target):
# search space is nums[left…right]
(left, right) = (0, len(nums) - 1)
# loop till the search space is exhausted
while left <= right:
# find the mid-value in the search space and
# compares it with the target
mid = (left + right) // 2
# if the key is found, return its index
if target == nums[mid]:
return mid
# if right half nums[mid…right] is sorted and `mid` is not
# the key element
if nums[mid] <= nums[right]:
# compare key with nums[mid] and nums[right] to know
# if it lies in nums[mid…right] or not
if nums[mid] < target <= nums[right]:
left = mid + 1 # go searching in the right sorted half
else:
right = mid - 1 # go searching left
# if left half nums[left…mid] is sorted, and `mid` is not
# the key element
else:
# compare key with nums[left] and nums[mid] to know
# if it lies in nums[left…mid] or not
if nums[left] <= target < nums[mid]:
right = mid - 1 # go searching in the left sorted half
else:
left = mid + 1 # go searching right
# key not found or invalid input
return -1
if __name__ == ‘__main__’:
nums = [9, 10, 2, 5, 6, 8]
key = 5
index = searchCircularList(nums, key)
if index != -1:
print('Element found at index', index)
else:
print('Element found not in the list')
Given a sorted array of n integers and a target value, determine if the target exists in the array in logarithmic time
idea is to use binary search which is a Divide and Conquer algorithm. Like all divide-and-conquer algorithms, binary search first divides a large array into two smaller subarrays and then recursively (or iteratively) operate the subarrays. But instead of working on both subarrays, it discards one subarray and continues on the second subarray. This decision of discarding one subarray is made in just one comparison
We know that at each step of the algorithm, our search space reduces to half. That means if initially, our search space contains n elements, then after one iteration it contains n/2, then n/4 and so on…
n —> n/2 —> n/4 —> … —> 1
Suppose our search space is exhausted after k steps. Then,
n/2k = 1 n = 2k k = log2n
for avoid integer overflow:
mid = high – (high – low)/2;
mid = low + (high – low)/2
############### code############ # Function to determine if a `target` exists in the sorted list `nums` # or not using a binary search algorithm def binarySearch(nums, target):
# search space is nums[left…right]
(left, right) = (0, len(nums) - 1)
# loop till the search space is exhausted
while left <= right:
# find the mid-value in the search space and
# compares it with the target
mid = (left + right) // 2
# overflow can happen. Use:
# mid = left + (right - left) / 2
# mid = right - (right - left) // 2
# target is found
if target == nums[mid]:
return mid
# discard all elements in the right search space,
# including the middle element
elif target < nums[mid]:
right = mid - 1
# discard all elements in the left search space,
# including the middle element
else:
left = mid + 1
# `target` doesn't exist in the list
return -1
###########################################
def binarySearch(nums, left, right, target):
# Base condition (search space is exhausted)
if left > right:
return -1
# find the mid-value in the search space and
# compares it with the target
mid = (left + right) // 2
# overflow can happen. Use below
# mid = left + (right - left) / 2
# Base condition (a target is found)
if target == nums[mid]:
return mid
# discard all elements in the right search space,
# including the middle element
elif target < nums[mid]:
return binarySearch(nums, left, mid - 1, target)
# discard all elements in the left search space,
# including the middle element
else:
return binarySearch(nums, mid + 1, right, target)
Given a circularly sorted integer array, find the total number of times the array is rotated. Assume there are no duplicates in the array, and the rotation is in the anti-clockwise direction.
linear search : min -> A[0] miniindex -> 0 for i 1 -> n-1 if A[i] < min -> min= A[i] , minindex= i
We can easily solve this problem in O(log(n)) time by modifying the binary search algorithm. We have already reduced the problem to find out the first element of the sorted sequence. The first element (Pivot) has one special property (let’s call it the pivot’s property) – both the next and previous element of the pivot element are greater than it. No other array element will have this property except the pivot element. Since the array is circularly sorted,
If the pivot is the last element, then the first element will be considered its next element.
If the pivot is the first element, then the last element will be considered its previous element.
We know that the middle element always divides the array into two subarrays, and the pivot element can lie only in one of these halves. It is worth noticing that at least one of these subarrays will always be sorted. If middle element happens to be the point of rotation (minimum element), then both left and right subarrays are sorted. Still, in any case, one half (subarray) must be sorted, and we will use this property to discard the left half or the right half at each iteration of the binary search.
use iterative binary search:
we have 2 index, low =0 and high = len(arr)-1
case1 : A[low] <=A[high]: return low as the minindex
# calculate next and prev index
next = (mid -1+ len(arr) % len(arr)
prev = (mid+1) % len(arr)
case 2: arr[mid] <= arr[next] and arr[mid] <= arr[prev]
return mid
case 3:
arr[mid]>=arr[low]: the min index cannot be in this range
low = mid+1
case 4:
arr[mid] <= arr[high]:
high = mid-1
#################### # Function to find the total number of times the list is rotated def findRotationCount(nums):
# search space is nums[left…right]
(left, right) = (0, len(nums) - 1)
# loop till the search space is exhausted
while left <= right:
# if the search space is already sorted, we have
# found the minimum element (at index `left`)
if nums[left] <= nums[right]:
return left
mid = (left + right) // 2
# find the next and previous element of the `mid` element (in circular manner)
next = (mid + 1) % len(nums)
prev = (mid - 1 + len(nums)) % len(nums)
# if the `mid` element is less than both its next and previous
# neighbor, it is the list's minimum element
if nums[mid] <= nums[next] and nums[mid] <= nums[prev]:
return mid
# if nums[mid…right] is sorted, and `mid` is not the minimum element,
# then the pivot element cannot be present in nums[mid…right],
# discard nums[mid…right] and search in the left half
elif nums[mid] <= nums[right]:
right = mid - 1
# if nums[left…mid] is sorted, then the pivot element cannot be present in it;
# discard nums[left…mid] and search in the right half
elif nums[mid] >= nums[left]:
left = mid + 1
# invalid input
return -1
Given a circularly sorted integer array, search an element in it. Assume there are no duplicates in the array, and the rotation is in the anti-clockwise direction.
modify the iterative binary serach
mid -> right - (right- left)//2 case1: A[mid]== A[target] return mid case2: right side sorted A[mid ... right] if A[mid] <=target < A[high]: left = mid+1 els:e right = mid -1 else: if A[left] <= target < A[mid]: right = mid-1 else: left = mid+1
O(log(n))
################# code############ # Function to find an element in a circularly sorted list def searchCircularList(nums, target):
# search space is nums[left…right]
(left, right) = (0, len(nums) - 1)
# loop till the search space is exhausted
while left <= right:
# find the mid-value in the search space and
# compares it with the target
mid = (left + right) // 2
# if the key is found, return its index
if target == nums[mid]:
return mid
# if right half nums[mid…right] is sorted and `mid` is not
# the key element
if nums[mid] <= nums[right]:
# compare key with nums[mid] and nums[right] to know
# if it lies in nums[mid…right] or not
if nums[mid] < target <= nums[right]:
left = mid + 1 # go searching in the right sorted half
else:
right = mid - 1 # go searching left
# if left half nums[left…mid] is sorted, and `mid` is not
# the key element
else:
# compare key with nums[left] and nums[mid] to know
# if it lies in nums[left…mid] or not
if nums[left] <= target < nums[mid]:
right = mid - 1 # go searching in the left sorted half
else:
left = mid + 1 # go searching right
# key not found or invalid input
return -1
Given a sorted integer array, find the index of a given number’s first or last occurrence. If the element is not present in the array, report that as well.
The standard binary search terminates as soon as any occurrence of the given target element is found. To find the given element’s first occurrence, modify the binary search iteratively to continue searching even on finding the target element. Instead, update the result to mid and search towards the left (towards lower indices), i.e., modify our search space by adjusting high to mid-1 on finding the target at mid-index.
for first occurrence:
if A[mid]== target: result = mid , right= mid-1 (rasto mibande)
for the last occurrence:
if A[mid]== target: result = mid , left= mid+1 (chapo mibande)
###################### code############ def findFirstOccurrence(nums, target):
# search space is nums[left…right]
(left, right) = (0, len(nums) - 1)
# initialize the result by -1
result = -1
# loop till the search space is exhausted
while left <= right:
# find the mid-value in the search space and compares it with the target
mid = (left + right) // 2
# if the target is located, update the result and
# search towards the left (lower indices)
if target == nums[mid]:
result = mid
right = mid - 1
# if the target is less than the middle element, discard the right half
elif target < nums[mid]:
right = mid - 1
# if the target is more than the middle element, discard the left half
else:
left = mid + 1
# return the leftmost index, or -1 if the element is not found
return result
################## code def findLastOccurrence(nums, target):
# search space is nums[left…right]
(left, right) = (0, len(nums) - 1)
# initialize the result by -1
result = -1
# loop till the search space is exhausted
while left <= right:
# find the mid-value in the search space and compares it with the target
mid = (left + right) // 2
# if the target is located, update the result and
# search towards the right (higher indices)
if target == nums[mid]:
result = mid
left = mid + 1
# if the target is less than the middle element, discard the right half
elif target < nums[mid]:
right = mid - 1
# if the target is more than the middle element, discard the left half
else:
left = mid + 1
# return the leftmost index, or -1 if the element is not found
return result
Given a sorted integer array containing duplicates, count occurrences of a given number. If the element is not found in the array, report that as well.
We can easily solve this problem in O(log(n)) time by modifying the binary search algorithm. The idea is to find the index of the first and last occurrence of the given number and return one more than the difference between two indices. We have already discussed how and find the first and last occurrence of a number in O(log(n)) time in the previous post
iterative binary search
we add an argument to the function called serachFirst:
then if A[mid] == target:
if searchFirst: right = mid-1
else: left = mid+1
then in a function we call the first function with :
serachFirst = True –> first idx
serachFirst = False –> last idx
final_res = lastidx- firstidx+1 ################## code def binarySearch(nums, target, searchFirst):
# search space is nums[left…right]
(left, right) = (0, len(nums) - 1)
# initialize the result by -1
result = -1
# loop till the search space is exhausted
while left <= right:
# find the mid-value in the search space and compares it with the target
mid = (left + right) // 2
# if the target is found, update the result
if target == nums[mid]:
result = mid
# go on searching towards the left (lower indices)
if searchFirst:
right = mid - 1
# go on searching towards the right (higher indices)
else:
left = mid + 1
# if the target is less than the middle element, discard the right half
elif target < nums[mid]:
right = mid - 1
# if the target is more than the middle element, discard the left half
else:
left = mid + 1
# return the found index or -1 if the element is not found
return result
Given a sorted array of non-negative distinct integers, find the smallest missing non-negative element in it.
We can easily solve this problem in O(log(n)) time by modifying the recursive binary search algorithm. The idea is to compare the mid-index with the middle element. If both are the same, then the mismatch is in the right subarray; otherwise, it lies in the left subarray.
O(log(n))
code################
def findSmallestMissing(nums, left=None, right=None):
# initialize left and right
if left is None and right is None:
(left, right) = (0, len(nums) - 1)
# base condition
if left > right:
return left
mid = left + (right - left) // 2
# if the mid-index matches with its value, then the mismatch
# lies on the right half
if nums[mid] == mid:
return findSmallestMissing(nums, mid + 1, right)
# mismatch lies on the left half
else:
return findSmallestMissing(nums, left, mid - 1)
Given a sorted integer array, find the floor and ceil of a given number in it. The floor and ceil map the given number to the largest previous or the smallest following integer in the array.
modify binary search iteratively
findCeil(nums[low, high], x)
Initialize ceil to -1 and iterate till our search space is exhausted.
If x is equal to the middle element, it is the ceil.
If x is less than the middle element, the ceil exists in subarray nums[low…mid]; update ceil to the middle value and reduce our search space to the left subarray nums[low…mid-1].
If x is more than the middle element, the ceil exists in the right subarray nums[mid+1…high].
findFloor(nums[low, high], x)
Initialize floor to -1 and iterate till our search space is exhausted.
If x is equal to the middle element, it is the floor.
If x is less than the middle element, the floor exists in the left subarray nums[low…mid-1].
If x is more than the middle element, the floor exists in subarray nums[mid…high]; update floor to the middle element and reduce our search space to the right subarray nums[mid+1…high].
####### code########### def getCeil(nums, x):
# search space is nums[left…right]
(left, right) = (0, len(nums) - 1)
# initialize ceil to -1
ceil = -1
# loop till the search space is exhausted
while left <= right:
# find the mid-value in the search space
mid = (left + right) // 2
# if `x` is equal to the middle element, it is the ceil
if nums[mid] == x:
return nums[mid]
# if `x` is less than the middle element, the ceil exists in the
# sublist nums[left…mid]; update ceil to the middle element
# and reduce our search space to the left sublist nums[left…mid-1]
elif x < nums[mid]:
ceil = nums[mid]
right = mid - 1
# if `x` is more than the middle element, the ceil exists in the
# right sublist nums[mid+1…right]
else:
left = mid + 1
return ceil
def getFloor(nums, x):
(left, right) = (0, len(nums) - 1)
# initialize floor to -1
floor = -1
# loop till the search space is exhausted
while left <= right:
# find the mid-value in the search space
mid = (left + right) // 2
# if `x` is equal to the middle element, it is the floor
if nums[mid] == x:
return nums[mid]
# if `x` is less than the middle element, the floor exists in the left
# sublist nums[left…mid-1]
elif x < nums[mid]:
right = mid - 1
# if `x` is more than the middle element, the floor exists in the
# sublist nums[mid…right]; update floor to the middle element
# and reduce our search space to the right sublist nums[mid+1…right]
else:
floor = nums[mid]
left = mid + 1
return floor
Given a nearly sorted array such that each of the n elements may be misplaced by no more than one position from the correct sorted order, search a given element in it efficiently. Report if the element is not present in the array.
We can easily solve this problem in O(log(n)) time by modifying the binary search algorithm. The idea is to compare the target number with elements at A[mid-1], A[mid], and A[mid+1], where mid is the middle index of our search space A[low…high]. If the target is found, return the corresponding index; otherwise, reduce our search space to the left subarray A[low…mid-2] or right subarray A[mid+2…high] depending upon if the middle element is less than the target number or not.
code########
def searchElement(nums, target):
# search space is nums[left…right]
(left, right) = (0, len(nums) - 1)
# loop till the search space is exhausted
while left <= right:
# find middle index `mid` and compare nums[mid-1], nums[mid], and
# nums[mid+1] with the target number
mid = (left + right) // 2
# return `mid` if the middle element is equal to the target number
if nums[mid] == target:
return mid
# return `mid-1` if nums[mid-1] is equal to target number
elif mid - 1 >= left and nums[mid - 1] == target:
return mid - 1
# return `mid+1` if nums[mid+1] is equal to target number
elif mid + 1 <= right and nums[mid + 1] == target:
return mid + 1
# if the middle element is less than the target number,
# reduce search space to the right sublist nums[mid+2…right]
elif target > nums[mid]:
left = mid + 2
# if the middle element is greater than the target number,
# reduce search space to the right sublist nums[left…mid-2]
else:
right = mid - 2
# invalid input or number present is not on the list
return -1
Given a sorted binary array, efficiently count the total number of 1’s in it.
We can easily solve this problem in O(log(n)) time using recursion by taking advantage of the fact that the input is sorted (i.e., all 0’s, followed by all 1’s). The idea is to split the array into two halves and recur for both halves. If the last element of the subarray is 0, then all 0’s are present in it since it is sorted, and we return 0 from the function. If the first array element is 1, then all its elements are 1’s only since the array is sorted, and we return the total number of elements in that partition
`` def count case1 : nums[right]==0 --> return 0 case 2: nums[left]== 1 --> return right-left+1 mid = (right+left)//2 return count(nums, left, mid) +count(nums, mid+1, right)```
################## code############# def count(nums, left=None, right=None):
# base case
if not nums:
return 0
# Initialize left and right
if left is None and right is None:
left, right = 0, len(nums) - 1
# if the last element in the list is 0, no 1's can
# be present since it is sorted
if nums[right] == 0:
return 0
# if the first element in the list is 1, all its elements
# are ones only since it is sorted
if nums[left] == 1:
return right - left + 1
# divide the list into left and right sublist and recur
mid = (left + right) // 2
return count(nums, left, mid) + count(nums, mid + 1, right)
Given an integer array, find the peak element in it. A peak element is an element that is greater than its neighbors. There might be multiple peak elements in an array, and the solution should report any peak element.
modified recursive binary search.
O(log(n))
def findPeak
case 1: (mid = len(A)-1 or A[mid]<=A[mid+1]) and (mid==0 or A[mid] >= A[mid-1]): retunr mid
case2 if mid-1 >0 and A[mid] <a>= 0 and nums[mid - 1] > nums[mid]:
return findPeak(nums, left, mid - 1)
~~~</a>
# If the right neighbor of `mid` is greater than the middle element,
# find the peak recursively in the right sublist
return findPeak(nums, mid + 1, right)
def findPeakElement(nums) -> int:
# base case
if not nums:
exit(-1)
index = findPeak(nums)
return nums[index]</a>
