-1
\$\begingroup\$

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

\$\endgroup\$
  • 5
    \$\begingroup\$ I believe the fastest will be O(log n) by divide & conquer. \$\endgroup\$ – Jonathan Allan Mar 18 '18 at 21:15
  • 8
    \$\begingroup\$ Well, too easy for a fastest-algorithm, IMO. Now the challenge is essentially closed. \$\endgroup\$ – user202729 Mar 19 '18 at 1:08
  • 1
    \$\begingroup\$ @nicael: You've chosen to score this question by asymptotic complexity (fastest-algorithm tag description: "Fastest-algorithm competitions are won by the answer with the smallest asymptotic time complexity. For challenges based on actual runtime, use [fastest-code] instead.") If you're thinking of some constant-factor improvement, it doesn't matter for this challenge. \$\endgroup\$ – user2357112 Mar 19 '18 at 1:54
  • 1
    \$\begingroup\$ That's average-case O(log(n)), and using the position of the max as a parameter in the time complexity opens things up to too much ambiguity - you could just as easily make the algorithm O(log(n-m)), or O(log(distance of max from array center)), or any number of other ways of prioritizing the search. \$\endgroup\$ – user2357112 Mar 19 '18 at 6:44
  • 1
    \$\begingroup\$ @nicael "Fastest" could mean fastest on average or fastest in the worst case. If it's worst-case, O(log(m)) is indistinguishable from O(log(n)), as m can be anywhere in 0...n-1. If it's on average, O(log(m)) could be asymptotically better, provided there's a strong bias towards smaller m. \$\endgroup\$ – ngn Mar 19 '18 at 11:06
3
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ You can improve by replacing left_bound + (right_bound - left_bound) / 2 by (right_bound + left_bound) / 2, which is equivalent. \$\endgroup\$ – Angelorf Mar 22 '18 at 16:35
  • \$\begingroup\$ @Angelorf I would assume that such an optimisation could be performed by the compiler. If it is not, since this challenge is about finding a well performing algorithm, altering the formula in this manner does not change the algorithm's asymptotic time complexity. \$\endgroup\$ – Jonathan Frech Mar 22 '18 at 17:31
  • \$\begingroup\$ My suggestion can't make it slower and it could make it faster for some compilers in some interpretation of the word 'fast'. It's just a suggested edit. \$\endgroup\$ – Angelorf Mar 26 '18 at 21:49
2
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ Are you allowed to take the length as input, even though it isn't needed? \$\endgroup\$ – 12Me21 Mar 18 '18 at 23:35
  • \$\begingroup\$ @12Me21 Testing Array.length is probably O(1) in most - if not all - JS engines, but I don't think this is part of the specification (in other words, it could be O(n) just as well). Since taking the length as input was explicitly allowed by the OP, I guess it doesn't hurt to do so. \$\endgroup\$ – Arnauld Mar 19 '18 at 0:03
  • \$\begingroup\$ I would assume that Array.length is an actual property on all platforms (thus accessing it is O(1)), simply due to the fact that the length cannot be calculated from the number of items in the array or the index of the last item. \$\endgroup\$ – ETHproductions Mar 19 '18 at 3:24
  • \$\begingroup\$ @ETHproductions Thanks for your feedback. I went ahead and updated it accordingly. \$\endgroup\$ – Arnauld Mar 19 '18 at 9:42
0
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.