Binary search of an element in a sorted array

We didn't learn C at the same place. Have you tried compiling your code?

Where did you get this code?

In the view function, why do you change the values of inf and sup?

With a little imagination, it could resemble a binary search.

There are several iterative implementations of this algorithm.

Do a search on the web.

P.S. A binary search is done on a sorted array (which is the case here)

Maybe before you dive into this exercise, you should correct (understand) this one https://forums.commentcamarche.net/forum/affich-38004912-exercice-sur-les-pointeurs#dernier

When I was little, the Dead Sea was just sick.
George Burns

Several errors for so little code:
This is not the correct way to declare an enum or a typedef.
There is a bool type in <stdbool.h>
The definitions of enums and arrays are done with { } instead of ( )
You are using *elt while elt has not been defined as a pointer (see the link from Whismeril).
In view(), the loop goes from 5 to 32 instead of from inf to sup. This leads me to believe there is a misunderstanding regarding parameter passing.

You will not display what you think you are displaying.

In fun(), the recursive calls do not return anything.
And the algorithm itself is not correct.

edit: it works but requires going down to an interval of a single element.

Hello,

Preliminary remarks

Thank you for sharing your code snippets as explained here in the future and especially for properly indenting them; it will help you avoid programming errors. I also recommend you to systematically open and close pairs of braces after every if/else/for/while statement and to go to a new line after each { and } to make your code more readable and likely avoid programming errors on longer projects.

Furthermore, it would be good to use a less vague discussion title and explain the purpose of your program.

Feedback on the code

Line 3 is poorly written:

• as pointed out by Pierrot #3, the bool type is used as follows:

#include <stdbool.h> int main() { bool b1 = true; bool b2 = true; return 0; } 

Line 14 is "confusing" because if I understand your program correctly, inf is always supposed to be less than or equal to sup, so I would rather distinguish:

if (inf < sup) { // Continue tightening [inf, sup] } else if (inf == sup) { // Check if elt is indeed here } else { // Error, we should not be in this case }

Line 15 seems very suspect to me.

• If you want to perform a test (which, in my opinion, is the bug you're looking for and that brought you here, by the way), you should write:

if (vec[med] == *elt)

• Currently, you are assigning *elt to vec[med]. The result of this operation is the value assigned to vec[med]. If this value is non-zero then the test is true, otherwise it is false. This means that each time you perform this test, you modify the content of vec. I doubt this is what you meant to write. Since writing = instead of == can easily happen, your compiler usually warns you. In cases where you indeed want to perform the test plus the assignment, the compiler expects you to emphasize this by double parentheses in the if. In your case, it would be equivalent to writing:

if ((vec[med] = *elt))

How to display part of an array

I will rephrase it more precisely as: how to display a slice of the array tab of type int *, from index i (inclusive) to index j (exclusive).

#include <stdio.h> void print_tab( int * tab, size_t num_elements, size_t i, size_t j ) {     printf("[");     for (size_t k = i; k < j; k++) {         printf(" %d", tab[k]);     }         printf(" ]\n"); }      int main() {     int tab[] = {10, 20, 30, 40, 50, 60};     size_t num_elements = sizeof(tab) / sizeof(int);     print_tab(tab, num_elements, 0, 6); // [ 10 20 30 40 50 60 ]     print_tab(tab, num_elements, 2, 5); // [ 30 40 50 ]     print_tab(tab, num_elements, 2, 3); // [ 30 ]     print_tab(tab, num_elements, 2, 2); // [ ]     print_tab(tab, num_elements, 2, 1); // [ ]     return 0;       } 

Iterative version

In broad strokes, you need to replace your recursive call and use a while loop that you will exit when a stopping criterion is reached.

The first thing to do is to understand what these stopping criteria are, and how to ensure that with each loop iteration, you strictly reduce your search space.

Since your goal here is to tighten your indices inf and sup to find med, it is likely that your stopping criterion consists of checking if inf == sup and making sure that at each loop iteration, either inf gets closer to sup, or sup gets closer to inf.

Good luck

@mamiemando, I wonder if Steve17_17 understood how to calculate the length of an array with the formula:
    num_elements = sizeof(tab) / sizeof(tab[0]);
This variable is not used in the print_tab() function.
I assume you left it up to him to calculate himself if the bounds i and j were correct.
Mathematically: 0 <= i < j <= num_elements
One thing that can confuse a beginner looking for an implementation is the fact that there are two possible variants:
Firstly, inf is the index of the first element and sup is the index of the last element.
Secondly, inf is always the index of the first, but sup is the index of the next element after the last.
In this second variant, sup - inf is the length of the sub-array to search.
The test for tightening and adjusting inf or sup relative to med is slightly different.
The idea of tightening around the searched element is correct but not necessarily the most efficient.
I give a simple example with the following array:
[10, 20, 30, 40, 50, 60, 70]
with the second variant, inf = 0 and sup = 7 and I am looking for the value 40.
Then, med = (inf + sup) / 2 = (0 + 7) / 2 = 3
And indeed 40 is located at index 3. I therefore find it on the first recursion (or iteration)
The idea is to test the bounds and evaluate the value of med immediately after.
If inf > sup or inf >= sup depending on the variant, we have not found it.
Otherwise, we immediately calculate the value of med and test right away if the value at that position is the sought value.
If so, we exit with true or the index where the sought value is located.
Otherwise, we search in what precedes or follows depending on whether this value comes before or after that of position med.
First variant: fun(tab, inf, med-1) or fun(tab, med+1, sup)
Second variant: fun(tab, inf, med) or fun(tab, med+1, sup)

Alright, thank you very much, I’ve noted it down.