Skip to content

Instantly share code, notes, and snippets.

@VasudhaJha
Created May 6, 2019 12:35
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 VasudhaJha/dd53153bafd088633edfb94027ba7580 to your computer and use it in GitHub Desktop.
Save VasudhaJha/dd53153bafd088633edfb94027ba7580 to your computer and use it in GitHub Desktop.
Swift implementation of the classic Find a peak problem
func findAPeak(arr: [Int], low: Int, high: Int, size: Int) -> Int {
//Find index of the middle element
let mid = low + (high - low)/2
// Compare the middle element with its neighbours if they exist
if (mid == 0 || arr[mid - 1] <= arr[mid]) && (mid == size - 1 || arr[mid + 1] <= arr[mid]) {
return mid
}
// If the middle neighbour is not the peak and the left neighbour is greater than it, then the left half must have the peak element
else if (mid > 0 && arr[mid - 1] > arr[mid]) {
return findAPeak(arr: arr, low: low, high: mid - 1, size: size)
}
// If middle element is not the peal and its right neighbour is greater than it, then the right half must have the peak element
else {
return findAPeak(arr: arr, low: (mid + 1), high: high, size: size)
}
}
let array = [10, 20, 15, 60, 90]
let size = array.count
let peak = findAPeak(arr: array, low: 0, high: size - 1, size: size)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment