## Given two crystal balls that will break if dropped from a high enough distance, determine the exact spot in which it will break in the most optimised way.

Prerequisite: Binary Search, Big-O Notation

Let’s consider the collection of various distances as a boolean array. In this array, an entry is `true`

if the **crystal ball will break** at that distance, and `false`

**if the ball will not break**. The `false`

and `true`

entries are contiguous, so the array will be like this, `[false, false, false, true, true]`

or `[false, true, true]`

, and `true`

entries will always come after `false`

entries (if `true`

entries exist). We have to find the index of the first entry where the value is `true`

.

**Linear Search** will work but needs **O(n)** time.

- We’ll go through each entry and check if it’s
`true`

. In the worst case, only the last entry is`true`

, and we’ll have to go through the whole array.

```
// O(n)
function solution(breaks: boolean[]): number {
for (let index = 0; index < breaks.length; index++) {
if (breaks[index]) return index;
}
return -1;
}
```

**Binary Search** will also need **O(n)** time.

Consider an array like this

`[false, false, false, true, true]`

. In typical Binary Search fashion, let's halve the array and check the entry.If the entry is

`true`

, how can we determine if this is the first`true`

entry? We have to go backwards in the array from our current position until we find a`false`

and the last`true`

index is our result.If the value is

`false`

we’ll move to the**right half**. We keep doing this until we find a true value, and then move to step 1.

To measure the complexity, let’s assume a worst-case where all the values are

`true`

. For such an array of length**1000**, the loops will run exactly**502**times. For 10000, it becomes 5002, and it goes on proportionately. So we can see that the number of iterations is roughly half, so it’s**O(n/2),**which is equivalent to O(n) without the constant factor.

```
// O(n/2) => O(n)
function solution(breaks: boolean[]): number {
let lo = 0;
let resultIndex = null;
while (lo < breaks.length - 1) {
const mid = Math.floor(lo + (breaks.length - lo) / 2);
if (!breaks[mid]) {
lo = mid;
continue;
}
resultIndex = mid;
while (breaks[resultIndex]) {
--resultIndex;
}
break;
}
return resultIndex ? resultIndex + 1 : -1;
}
```

**Optimised Linear Search can do this in** O(√n) time!

**Strategy:**What if, unlike linear search where we go over the entries one by one, we jump a certain distance in each iteration, and then go back a bit if we already crossed the first`true`

entry? The happy path would look like this,We’ll start iterating from the beginning of the array and jump a certain amount (√n) in each iteration.

If we find a

`true`

entry, we know for sure that the entry itself or some other entry before it will be the first`true`

entry.- We iterate from our current index to the last iteration index where we found the
`false`

entry, and the first`true`

entry will be somewhere in between.

- We iterate from our current index to the last iteration index where we found the

**Example:**Let’s say we have an array like`[false, false, false, true, true, true]`

. Here, if we jump by**√n**each time from the`0th index`

, we’ll find a`true`

entry at`4th index`

in the`2nd iteration`

. As the entry itself isn’t the first`true`

entry, we can iterate backwards from`4th index`

to the last`false`

index. This inner iteration will run**√n**times at worst-case, but we'll find the result, guaranteed!**Complexity:**As we’re jumping**√n**distance each time, the maximum number of iterations can be`n/√n`

. If the jump is successful, that is we’ve found a`true`

value, then we’re iterating a partial array with a length of**√n**. So the total number of iterations is`(n/√n) + √n`

, which denotes the complexity is`O(√n)`

. This is significantly less than the Linear/Binary Search approach.

```
// O(√n)
function solution(breaks: boolean[]): number {
const jumpAmount = Math.floor(Math.sqrt(breaks.length));
for (
let outerIndex = 0;
outerIndex < breaks.length;
outerIndex += jumpAmount
) {
if (!breaks[outerIndex]) continue;
for (
let innerIndex = outerIndex;
innerIndex >= outerIndex - jumpAmount;
innerIndex--
) {
if (!breaks[innerIndex]) {
return innerIndex + 1;
}
}
}
return -1;
}
```