Skip to content

Instantly share code, notes, and snippets.

@LindaLawton
Created March 23, 2017 11:38
Show Gist options
  • Star 2 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save LindaLawton/d1d84cf286ca6e4d00c5be28d8698719 to your computer and use it in GitHub Desktop.
Save LindaLawton/d1d84cf286ca6e4d00c5be28d8698719 to your computer and use it in GitHub Desktop.
logarithmic peak finding solution in C#
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
}
}
}
}
}
@MrIBond
Copy link

MrIBond commented Sep 9, 2018

{ 6, 5, 4, 3, 5, 1, 3, 6 }

@jbollman7
Copy link

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?

@jbollman7
Copy link

jbollman7 commented Dec 2, 2020

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