Find a missing element in a sorted list

Question

I've made a program to find the missing element (if there's one) in a sequential list:

Program criteria:

Returns -1 if a list is sequential, otherwise the missing element in a non-sequential list is returned.

To perform binary search, we need a key to half the problem size. Here the key is to find the distance between the index (low, high) and their corresponding values.

Compilation procedure:

gcc -Wall -g testList.c -o testList
./testList

---

#include<stdio.h>
int bSearch(int array[], int low, int high){
 int mid = (low + high) / 2;
 if(high == low + 1){
 if(array[high] > array[low] +1){
 return array[low] +1;
 }else{
 return -1;
 }
 }
 if(array[mid] - array[low] == mid - low){
 return bSearch(array, mid, high);
 }else if(array[mid] - array[low] > mid - low){
 return bSearch(array, low, mid);
 }else{
 return -1;
 }
}
int main(void){
 int array [] = {22, 23, 24, 25, 26, 27, 28, 30};
 int upperBound = (sizeof(array)/sizeof(array[0]))-1;
 printf("%d\n", bSearch(array, 0, upperBound));
 return 0;
}

My questions:

1. Why does removing the else{} case cause the compiler to give a warning for it?

2. Can the base case look more elegant?

3. For code elegance and optimization, can this code be improved?

• Denis: I don't think I can help you with an answer as I'm not fluent in C but I can tell you that removing the else{} will cause error because not all method paths return value.
• overexchange: @denis Can you add datastructures tag?
• Jamal: @overexchange: No, we've destroyed that tag, so it shouldn't be added anymore.
• chux: "removing the else{} case" --> Which else are you asking about? Posting sample code without the else would help clarify the question.
• overexchange: @chux else working with else if

Answer 1

Why does removing the else{} case cause the compiler to give a warning for it?

The compiler will indeed issue a warning if a value-returning function doesn't return a value for every path. Ignoring this warning could then cause undefined behavior.

If you intend for bSearch() to return -1 on failure, then you can put just one return -1; at the very end of the function and remove the elses that return -1.

• overexchange: My point is, What is the chance that you get to very end? Do you think there is a chance? Give me a case where we can get to very end
• Jamal: @overexchange: What I'm saying is that it's a possible alternative for having those elses. Otherwise, you can keep what you already have.
• Denis: Even if there is no way to get to the very end, you can't prove that to the compiler.