Why is the C binary search implementation passing an address instead of an array?

Question

I have this C binary search program:

#include <stdio.h>

typedef int element_t;

int less(a, b) {
  if (a < b)
    return 1;
  return 0;
}

element_t *binary_search(element_t x, element_t *a , int n) {
  if (n > 0) {
    int mid = n / 2;
    if (less(a[mid], x))
      return binary_search(x, a+mid+1 , n-mid-1);
    if (less(x, a[mid]))
      return binary_search(x, a, mid);
    return a+mid;
    }
  return NULL;
}

int main(){

  int a[5] = {1,2,3,4,5};
  printf("%d %d", &a[2], binary_search(3, a, 5));
  return 0;
}

I don't get this part a+mid+1, it is supposed to pass an array there, but an address is instead, how is that? and array a + an integer is about address.

I read online and I can't see what is going on, because online it says a+1 is the address of value at index 1.

I think you'll come to learn that the line between pointer and array is nearly academic at times. A pointer can be used like an array, as in `(a + n)` is `&a[n]` and `*(a + n)` is `a[n]`. A lot of the time it's just a matter of notation. In fact, in a lot of cases when you pass in what you think is an array, it "decays" to a pointer, something known as "array to pointer decay". In C arrays are really, *really* barebones. They're not proper constructs like in, say, Java or JavaScript. — tadman, May 29 '23 at 02:40
The problem is that &a[2] and binary_search return a pointer so to print it out you need to use %p instead of $d: https://onlinegdb.com/aDB1WCIjd — Jerry Jeremiah, May 29 '23 at 02:42
It might help to recall that an array is a contiguous region of memory, and a pointer can be used to address (contiguous regions of) memory. — Elliott Frisch, May 29 '23 at 02:42
might some some good reads [here](https://stackoverflow.com/questions/1461432/what-is-array-to-pointer-decay) — yano, May 29 '23 at 02:43
`int less(a, b) {` You shouldn't write dinosaur C from the 1970s/1980s... — Lundin, May 29 '23 at 13:08

Dioswison · Answer 1 · 2023-05-29T04:16:02.390

To answer your question we first need a few definitions.

What is an array?

An array is a collection of variables of the same type which are contiguous to each other. In C, the name of an array (in this case a) is a pointer to the memory position where the first element is located.

For example in this code:

#include <stdio.h>

int main(){

    int a[4]={0,1,2,3,4};
    int *ptr=&a;
    int *ptr_a=a;

    return 0;
}

Both pointers point to the same memory location

What is a pointer?

A pointer is a variable which stores a memory position. Pointers have special arithmetic, when you add 1 to a pointer you are not (always) moving to the next memory position, you are adding the "weight" of the pointer type.

For example, if you have a char pointer you add by 1 byte at a time, but with int pointer you add 4 bytes(on 64-bit systems) each time you add 1.

What happens with pointers and arrays?

Since the array name is converted to a pointer when you add a value to it, you are moving to the memory position your next element is located. And using the [i] operator is equivalent to *(array+i)

You can(this doesn't mean you should) use arrays and pointers indistinctively.

This is called "The Array/Pointer Duality Law"

It is actually converted to a pointer any time it is used in an rvalue context (a context where a value is needed). — Chris Dodd, May 29 '23 at 03:58
*using the `[i]` operator is equivalent to `*(array+i)`* It's not just equivalent - [it's **defined** that way](https://port70.net/~nsz/c/c11/n1570.html#6.5.2.1p2) — Andrew Henle, May 29 '23 at 14:44
If it is defined that way, it is equivalent, equivalent means "the same". What is the issue with that phrasing? (Not native speaker, maybe im getting something wrong?) — Dioswison, May 29 '23 at 20:34

score 2 · Answer 2 · answered May 29 '23 at 13:02

Unless it is the operand of the sizeof, _Alignof, or unary & operators, or is a string literal used to initialize a character array in a declaration, an expression of type "N-element array of T" will be converted, or "decay", to an expression of type "pointer to T" and the value of the expression will be the address of the first element of the array.

When you call a function with an array argument, such as

int arr[10];
...
foo( arr );

the compiler replaces the expression arr with something like

foo( &arr[0] );

and what the function receives is a pointer, not an array.

The a parameter in the binary_search function is a pointer, not an array, so you can do pointer arithmetic on it.

In a function parameter list any parameters declared as T a[N] or T a[] are "adjusted" to T *a; all three declare a as a pointer.

There is a reason for this behavior. The array subscript operation a[i] is defined as *(a + i) - given some starting address a, offset i elements and dereference the result.

However, array objects do not store an address; when you declare an array as

int a[10];

what you get in memory is

   +---+
a: |   | a[0]
   +---+
   |   | a[1]
   +---+
    ...
   +---+
   |   | a[9]
   +---+

Hence the conversion rule. Unfortunately, this means arrays lose their "array-ness" in most circumstances.

Why is the C binary search implementation passing an address instead of an array?

2 Answers2

What is an array?

What is a pointer?

What happens with pointers and arrays?