Въпросът ми е, защо задачата при тази поредица и това търсено число кава, че Output-a e 0, а не 3. В смисъл 4 го има пет пъти в поредицата 4 4 4 4 4 8 8 8. Защо трябва да върне 0, а не индекса на числото в средата, при положение, че Binary Search според условието трябва да започва в среадата, което ще рече, че веднага намира числото 4:

"Basically, it goes to the middle element and checks it has to continue searching to the left, or to the right." - отивам в средата, намирам 4 и приключвам. Никъде не пише: you need to find the first instance of the number. 

Извинявай не съм прочел внимателно въпроса.

Според мен е грешка в теста, няма как да върне 0 в този случай, според мен

И аз така си мисля...

Aко връщаше true/false, ок.

В случая, вие нарушавате The principle of least astonishment.

При положение, че връща индекс, всеки с поне малко опит в програмирането би очаквал да види или най-левия елемент, или -1. Въпросният пример е оставен там неслучайно, за да ви подскаже как програмата ви трябва да се държи при наличието на еднакви елементи.

Мммм... Всеки, който е наясно какво е двоично търсене ще е изненадан от този резултат, както и авторът на темата. За сравнение може да се тества с вградения BinarySearch(), който ще върне друго. Ако се иска поведение, различно от широко очакваното, трябва ясно да се опише в условието.

Вградения връща индекса на първия намерен ... хах, ново двайсе.

Разбира се, идеята е скорост, да се гарантира логаритмична сложност при търсене. Интересува ни има ли такъв елемент и ако да на кой индекс може да го намерим, не е особено нужно да се знае дали има друг по-напред, това са излишни операции. При линейно търсене се връща първият срещнат; понеже обхождането е от ляво надясно това е най-левият, няма смисъл в общия случай да търсим дали има други след това.

Прав си за скоростта, ама добре, че никога не съм ползвал държавния метод. Щях да си счупя главата, докато разбера защо ми връща някакви безумни индекси. Най-вероятно щях да реша, че не работя със сортирана колекция.

Иначе, като учих BinarySearch преди няколко месеца, открих и ей тоя хак:

if (arr[middle] == target)
{
   if (middle > 0 && arr[middle] == arr[middle - 1])
       return BinarySearch(target, left, middle - 1);

   return middle;
}

На практика си е logN отвсякъде. С малка промяна в условието може да го накараш да връща и най-десния, ако искаш.