Binary search-like algorithm to find local peak

Question

Please help me improve my coding style.

/*
Author: Muhammad Awais
Blog: http://uetianblogger.blogspot.com/

Description:
Divide and Conquer Rule. Binary Search like algorithm
to find local peak.It may or may not find global peak
of the array.

Parameters:
A[]= Array of elements
i=starting point
j=ending point

Algorithms Class Analysis:
Theta(log(n))
BigO(log(n))
Omega(1)

*/

#include <stdio.h>
#include <stdlib.h>
int Peak1D(int A[],int i,int j)
{
    //Middle point 
    int m=((i+j)/2);

    //If it comes to either corner of the array
    if (m==i || m==j)
    {
        return A[m];
    }
    //To find peak
    else
    {
        if (A[m+1]>A[m])
        {
            Peak1D(A,m+1,j);
        }
        else if (A[m-1]>A[m])
        {
            Peak1D(A,i,m-1);
        }
        else   return A[m];

    }

}


***UPDATE**

Following is my updated code bases on suggestions. Please review this too.*

/*
Author: Muhammad Awais
Blog: http://uetianblogger.blogspot.com/
Date: 16/11/2016
Description:
Divide and Conquer Rule. Binary Search like algorithm
to find local peak.It may or may not find global peak
of the array.

Parameters:
A[]= Array of elements
starting_pt=starting point
ending_pt=ending point

Algorithms Class Analysis:
Theta(log(n))
BigO(log(n))
Omega(1)

*/

#include <stdio.h>
#include <stdlib.h>
int Peak1D(int A[],size_t starting_pt,size_t ending_pt)
{
    //If length is zero
    if ((sizeof(A)==0))
    {
        return 0;
    }

    //Middle point
    int middle_pt=((starting_pt+ending_pt)/2);

    //If it comes to either end of the array
    if (middle_pt==starting_pt || middle_pt==ending_pt)
    {
        return A[middle_pt];
    }
    //To find local peak

    if (A[middle_pt+1]>A[middle_pt])
    {
        Peak1D(A,middle_pt+1,ending_pt);
    }

    else if (A[middle_pt-1]>A[middle_pt])
    {
        Peak1D(A,starting_pt,middle_pt-1);
    }

    return A[middle_pt];

}

Answer 1

1. Why else? The if() branch never continues.

   // Why `else`
   if (m==i || m==j) {
       return A[m];
   }
   else {
      ....
   
   // Alternative
   if (m==i || m==j) {
       return A[m];
   }
   ... rest of code
   

2. Does the above make a difference? Easier to see code is invalid as it is missing return paths

   if (A[m+1]>A[m])
   {
       Peak1D(A,m+1,j);
       // what happens here??? Looks like return missing
       // was return Peak1D(A,m+1,j); intended?
   }
   // Now do not need `else`
   // else if (A[m-1]>A[m])
   if (A[m-1]>A[m])
   {
       // Peak1D(A,i,m-1);
       return Peak1D(A,i,m-1);
   }
   // Now do not need `else`
   // else   return A[m];
   return A[m];
   

3. int i,int j --> Why type int here? Why not char or long long? The best is to use size_t. That is an unsigned type that is neither too narrow nor too wide for array indexing and size calculation.

   // int Peak1D(int A[],int i,int j)
   int Peak1D(int A[],size_t i,size_t j)
   

4. Consider more descriptive names. @Ron Beyer How about "left" and "right"? or "starting_point" "ending_point"?

   int Peak1D(int A[],size_t left,size_t right)
   

5. Code defensively. Users of your useful code will try things not intended. What happens when i>j? Likely bad things. Suggest adding some tests as assert() or other error handling code.

   #include <assert.h>
   
   ...
   assert(i <= j); // If assertion fails, code in debug mode exits with an error message
   

6. Use const for referenced data that is not modified. This allows additional optimizations and allows execution with constant data.

   int Peak1D(const int A[],int i,int j)
   
   // Sample usage 
   const int sample[] = { 1,2,3,4,5};
   printf("%d\n",  Peak1D(sample, 0,4));
   

7. Good top of file documentation. Suggest adding month/year or at least year.

8. Above all, watch functionality. This code seems odd as I would expect (A == {6,8}, i==0, j==1) to return 8, not 6. OTOH, comment did say local peak - Oh, well.

   // correct?
   if (m==i || m==j) {
      return A[m];
   }
   

9. Architecture style.: A loop could have replaced the recursive function calls. See little value to recursion here.

10. Indentation style. It is consistent, which is most important. I find it a bit too loose, but identation is a holy war. IMO, best to follow an automated group's coding standards.

Answer 2

Assuming the algorithm is correct, here are my inputs:

• FORMATTING

  • Spacing after any operator or commas. int A[],int i,int j A[m-1]>A[m]
  • Uniformity with braces. Always prefer to have braces for any block (if-else, for, while, do-while, etc.) even if its a single statement.
  • Indentation. Avoid extra lines if it does not add separation of logic like after the return A[m]; statement.

• NOMENCLATURE

  • Variable names: i, j , m ,A. Treat it like your child and give them the a name that explains their purpose :)
  • Function name: Peak1D -> getLocalPeak(). A function name, should preferably be a command.

• Return statements:

  • Have one return (debatable preference) OR
  • ensure every block has a return statement. Just an overview of the algorithm, shows that the function expects an int to be returned but some of your if-else block doesn't return anything.

• Redundant else : Else is not required if the earlier statement has a return.

• Some minimal optimisation: (i+j)/2 => (i+j)>>1 assuming i,j are positive.

Lastly, a thought to guide you to writing a good code. Your function should be able to express its story without any comments. Its name is the intent, its variables are the characters and the operations are the actions. Happy coding :)