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];
}

• jacwah: Welcome to Code Review! Could you edit your question to include some information on what your program does? The more you tell us about what your code does and what the purpose of doing that is, the easier it will be for reviewers to help you. Thanks!
• Ron Beyer: If i is the starting point, why not name the variable startingPoint instead? Same with j and m should be middle. Arrays don't have "corners", they have bounds, the word "corner" makes me think matrix, not 1D array. The outer else doesn't need to be there and can be eliminated entirely.
• user122750: Thank you for your review. Is there any place on web where I can submit my code to know how am I coding?

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.

• user122750: Best Answer. Thanks. But I have some questions.
• user122750: Best Answer. Thanks. But I have some questions. 1) What is the effect of adding extra else? 2) Please refer me for assert() and defensive coding. 3) How recursion is better than loop? 4) Indentation is really a problem in codeblocks. Any suggestions please? Thanks again for your great, thourough answer.
• chux: 1) Effect of extra else is a style one. When competing styles exists, convey similar information, the one with less text is tends to be understood quicker, with less effort. As with such style issues, see last part of #10.
• chux: 2) Defensieve coding does not assume to much about inputs. Your code behaved poorly if i > j. See en.wikipedia.org/wiki/Assertion_(software_development)
• chux: @user122750 3) Most of the time, when code can be looped, it is better than recursion. At least a loop does not chew up the stack. But this is a broad question.

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 :)

• user122750: Thanks for the answer. How do I post an edited code here? I have made improvements based on your review.
• thepace: Edit your question and either add another program or update this one with a note that this program has been edited.
• chux: Note that (i+j)/2 differs from (i+j)>>1 when i+j is negative - though not a typical function usage.
• thepace: Update my comment.