-2
\$\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\$
11
  • 5
    \$\begingroup\$ I believe the fastest will be O(log n) by divide & conquer. \$\endgroup\$ Mar 18, 2018 at 21:15
  • 8
    \$\begingroup\$ Well, too easy for a fastest-algorithm, IMO. Now the challenge is essentially closed. \$\endgroup\$
    – DELETE_ME
    Mar 19, 2018 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\$ Mar 19, 2018 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\$ Mar 19, 2018 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, 2018 at 11:06

3 Answers 3

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\$
3
  • \$\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, 2018 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\$ Mar 22, 2018 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, 2018 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\$
4
  • \$\begingroup\$ Are you allowed to take the length as input, even though it isn't needed? \$\endgroup\$
    – 12Me21
    Mar 18, 2018 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, 2018 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\$ Mar 19, 2018 at 3:24
  • \$\begingroup\$ @ETHproductions Thanks for your feedback. I went ahead and updated it accordingly. \$\endgroup\$
    – Arnauld
    Mar 19, 2018 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 and acknowledge you have read our privacy policy.

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