Помогите пожалуйста,задание кода такое что нужно выполнить поиск заданного значения

в массиве, используя линейный(первое вхождение) и бинарный (последнее вхождение)алгоритмы поиска. Проблема в том что бинарный поиск показывает последнее значение в некоторых ситуациях(зависит от того как заполниться рандомно массив) на одну ячейку раньше. Что не так в коде?
#include <iostream>
#include <algorithm>
using namespace std;
void linsearch(int* a, int n, int key) {
a[n] = key;
int i=0;
while (a[i] != key) i++;
if (i == n)
cout << "\nЭлемент не найден"<<endl;
else
cout << "\n\nЛинейный поиск:" << endl;
cout << "Первое вхождение элемента найдено на позиции под номером " << i+1<<"\n"<<endl;
};
void binsearch(int* a, int n, int key) {
int l = 0, r = n - 1, s;
bool Found = false;
while ((l <= r) && !Found)
{
s = (l + r) / 2;
if (a[s] == key)
Found = true;
else
if (a[s] < key)
l = s + 1;
else
r = s - 1;
}
cout << "================================================================";
cout << "\nБинарный поиск:";
if (Found == true) cout << "\nПоследнее вхождение элемента найдено на позиции под номером " <<s+1<< " \n"<<endl;
else cout << "Элемент не найден!\n";
}
int a[100];
int main() {
setlocale(LC_ALL, "Ru");
int I, n,l,r,s;
int key;
cout << "Элемент=";
cin >> key;
cout << "Введите размер массива:";
cin >> n;
for (I = 0; I < n; I++)
{
a[I] = rand() % 10;
cout <<a[I]<<" ";
}
sort(a, a + n);
cout << "\nОтсортированный массив" << endl;
for (I = 0; I < n; I++)
{
cout << "|" << a[I];
}
linsearch(a, n, key);
binsearch(a, n,key);
system("pause");
return 0;
}

Бинарный поиск должен искать в сортированном массиве, там понятия "первый" и "последний" как-то странно выглядят