Fastest to find the joint

Question

The input is an array (or space-separated string, as you wish), zero-indexed, consisting of one strictly increasing array and one strictly decreasing array (in this order, not other vice versa), each having a length of 2 at least. Example is:

-10 -2 4 18 38 46 28 19 10

The goal is to write the fastest algorithm to find the joint of two sorted arrays.

In other words, the output is the index of the greatest element. In the provided case the output should be 5.

The input is guaranteed not to contain repeating numbers.

It's obvious that this can be solved with O(n) with ease, so please provide more interesting faster answers :)

---

Other test cases (first line is input, second is output):

0 1 4 3
2

---

1 10 9 8 7 6 5 4 3 1
1

---

1 3 4 6 7 8 0 -10 -20
5

---

1 3 5 3 1
2

---

You could also accept the length of the array as additional input, if needed

Answer 1

C (gcc)

int find_joint(int *array, int length) {
	int left_bound = 0, right_bound = length - 1, joint = length / 2;

	while (array[joint-1] > array[joint] || array[joint] < array[joint+1]) {
		if (array[joint-1] < array[joint])
			left_bound = joint + 2;
		else
			right_bound = joint - 2;

		joint = left_bound + (right_bound - left_bound) / 2;
	}

	return joint;
}

Try it online!

Answer 2

JavaScript (ES6), O(log n)

Now assuming that accessing Array.length is always O(1) (as suggested by @12Me21 and @ETHproductions) and therefore not requiring the length to be passed as input anymore.

Returns a string describing the result (index + number of iterations).

f = (a, n = 1, min = 0, max = a.length - 1) => {
  let res = x => `Found index ${x} in ${n} iteration(s)`,
      mid;

  return (
    // only one slot left?
    max == min ? res(max) :

    // only two slots left?
    max == min + 1 ? res(a[max] > a[min] ? max : min) :

    // is the middle slot greater than its two neighbors?
    a[mid = min + max >> 1] > a[mid + 1] && a[mid] > a[mid - 1] ? res(mid) :

    // recursive call required
    a[mid] > a[mid + 1] ?
      f(a, n + 1, min, mid - 1)
    :
      f(a, n + 1, mid + 1, max)
  );
}

Try it online!

Answer 3

JavaScript (ES7)

function find_join(a, l) {
    p = 1.25 ** .5 - .5;
    n = 1;
    i = 0;
    j = l * p + .5 | 0;
    k = j * p + .5 | 0;
    x = a[j];
    y = a[k];
    while (l > 2) {
        n++;
        if (x > y) {
            l = j;
            j = k;
            k = j * p + .5 | 0;
            x = y;
            y = a[i + k];
        } else {
            i += k;
            l -= k;
            k = j - k;
            j = l * p + .5 | 0;
            y = x;
            x = a[i + j];
        }
    }
    return [n, a.indexOf(Math.max(...a.slice(i, i + l)), i)];
}

I was too lazy to write out the full l < 3 case.

This algorithm optimises the number of accesses of the array a. In practice this is not very useful, since the binary search always tests consecutive elements, which is not likely to be much slower than testing a single element.