Optimizing find on sorted list

Question

I came across a problem where we get a sorted list of numbers and at some point the numbers in the list start repeating, something like 0,1,2,3,4,5,6,7,8,8,8, we need to retrieve the position where the repetition started.

Below is the approach I've taken...

function find(arr) {  
  let max = arr.length-1
  let min = 0
  do {
    let iter = Math.round((min + max) / 2)
    if (arr[max] == arr[iter])
      max = iter
    else
      min = iter
  } while (min + 1 < max)
  return max
}

arr = [0,1,2,3,4,5,6,7,8,8,8]
console.log(find(arr))

arr = [0,1,2,2,2,2,2,2,2,2,2]
console.log(find(arr))

arr = [0,2,4,6,8,10,10]
console.log(find(arr))

Probably there is a recursive way, but I could not figure it out
Is there a more efficient way to solve this?

Answer 1

As bobra and Raymond Chen indicated, you can't do better than O(log n). However, you had also asked about a recursive solution. Here you go:

function find(arr, min_idx = 0, max_idx = arr.length - 1) {
  if (min_idx >= max_idx)
    return max_idx 
  let guess = Math.floor((min_idx + max_idx) / 2)
  if (arr[guess] == arr[max_idx])
    return  find(arr, min_idx, guess)  
  return find(arr, guess + 1, max_idx)
}

let arr = [0,1,2,3,4,5,6,7,8,8,8]
console.log(find(arr))

arr = [0,1,2,2,2,2,2,2,2,2,2]
console.log(find(arr))

arr = [2,4,6,8,10,10]
console.log(find(arr))

arr = [10,10,10]
console.log(find(arr))

Note that this also fixes a bug in your implementation. I've added a test case where yours gave the wrong answer when the first element was equal to the max.