Created
March 23, 2017 11:38
-
-
Save LindaLawton/d1d84cf286ca6e4d00c5be28d8698719 to your computer and use it in GitHub Desktop.
logarithmic peak finding solution in C#
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
using System; | |
namespace CsharpCodeExamples | |
{ | |
class Program | |
{ | |
//Peak Finding in C# O(Log N) | |
//If we take a look at a set of numbers: { 1, 3, 4, 3, 2, 1, 3, 6 } | |
// | |
//As with binary search the idea here is to split the data in half and throw away the data we dont need. | |
// | |
//We know that if we start in the middle we will look at the value 3: | |
// Three is less than both four and two. | |
// | |
//So what now? Which side do we jump to? | |
// | |
// If you think about it a minute if a number is grater than the number we are checking then | |
// there has be a peak on that side. | |
// | |
// So in our case four is greater than three so we will jump to the left and divide the set in half. | |
// | |
// We now have this set of numbers to consider: {1, 3, 4} | |
// Once again we want to start in the middle so we've selected the three here. | |
// Three is less than both one and four. | |
// | |
// So what now well four is larger than three so we jump to the right side. | |
// | |
// We now have a new set containg only {4}. | |
// Which is our peak | |
static void Main(string[] args) | |
{ | |
var data = new int[] { 1, 3, 4, 3, 5, 1, 3, 6 }; | |
FindAPeak(data, data.Length-1); | |
} | |
public static int FindAPeak(int[] data, int n) { | |
var low = 0; | |
var high = n; | |
while (true) | |
{ | |
n = (high + low) / 2; | |
if (data[n] >= data[n - 1] && data[n] >= data[n + 1]) | |
return n; // this is a peak | |
else if (data[n] <= data[n - 1]) | |
{ | |
high = n - 1; // Peak is lower | |
} | |
else if (data[n] <= data[n + 1]) | |
{ | |
low = n + 1; // Peak is higher | |
} | |
} | |
} | |
} | |
} |
With the input of var data = new int[] { 6, 5, 4, 3, 5, 1, 3, 6 };
Unhandled exception. System.IndexOutOfRangeException: Index was outside the bounds of the array.
at Program.FindAPeak(Int32[] data, Int32 n)
at Program.Main(String[] args)
Command terminated by signal 6
In this scenario, the program starts with 3(the middle) sees 4 is bigger and determines the peak is on left half. Evaluates 6,5,4. Sees 6 is larger, but cant go any further and errors?
The fix was to check if n == 0
while (true)
{
n = (high + low) / 2;
if ((n == 0 || data[n] >= data[n - 1]) && data[n] >= data[n + 1])
return n; // this is a peak
else if (data[n] <= data[n - 1])
{
high = n - 1; // Peak is lower
}
else if (data[n] <= data[n + 1])
{
low = n + 1; // Peak is higher
}
}
var data = new int[] { 6, 5, 4, 3, 5, 1, 3, 6 };
Output = Index 0
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
{ 6, 5, 4, 3, 5, 1, 3, 6 }