This was a very trivial problem so I decided to have some fun. Can you figure out the run time? Notice the search pruning from len = r+1, can you figure out another optimization?

```
import java.util.Random;
public class Solution {
public int searchInsert(int[] A, int target) {
Random rnd = new Random();
int len = A.length;
for(int i = 0; i < 10000; i++){
int r = Math.abs(rnd.nextInt())%len;
if(A[r] == target) return r;
if(A[r] > target){
if(r == 0) return r;
if(A[r-1] == target) return r-1;
else if(A[r-1]< target) return r;
len = r+1;
}else{
if(r == len-1) return r+1;
if(A[r+1] >= target) return r+1;
}
}
return 0;
}
}
```

This algorithm is non deterministic so your results may vary...up the `i`

counter to increase your accept chance (but dont make infinite loop).

The idea is to see at what values of `i`

you can consistently get accepted but by not doing an infinite loop.

If you cant find it in the bounds of `i`

then just return 0 and hope thats right!