Question

Нужно написать функцию bsearch, которая принимает на вход отсортированный по убыванию массив целых чисел и целое число X. В качестве результата функция должна возвращать индекс первого элемента массива, строго меньшего X. В Вашей реализации функция может принимать любое количество любых параметров, только 2 этих параметра обязательны.

Answer 1

// PascalABC.NET 3.3, сборка 1540 от 16.09.2017
// Внимание! Если программа не работает, обновите версию!

function bsearch(a:array of integer; x:integer):integer:=a.FindIndex(t->t<x);

begin
  var P:=ArrRandom(ReadInteger('n='),-50,50).OrderByDescending(t->t).ToArray;
  P.Println;
  var x:=ReadInteger('x=');
  var i:=bsearch(P,x)+1;
  if i>0 then Writeln('Индекс первого элемента, меньшего x, равен ',i)
  else Writeln('Все элементы больше х')
end.

Пример
n= 13
47 36 26 25 17 6 -8 -11 -23 -29 -31 -39 -39
x= -10
Индекс первого элемента, меньшего x, равен 8

Answer 2

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int bSearch(const vector<int> &array, int value)
{
   auto it = find_if(array.begin(), array.end(), [&](int v) {return v<value;});
   return distance(array.begin(), it + 1);
}
 
int main()
{
   vector<int> array = { 16, -13, 12, -8, 5, 4, 1, -2, -5 };
   sort(array.rbegin(), array.rend());
   for (auto i : array){
    cout << i << " ";
   }
   cout << endl << bSearch(array, 9) << endl;
   return 0;
}

Answer 3

Функция `bsearch` должна принимать отсортированный по убыванию массив целых чисел и целое число X в качестве входных параметров. Затем функция должна вернуть индекс первого элемента массива, строго меньшего X.

Вот пример реализации функции `bsearch` на языке Python:

def bsearch(arr, X):
    left = 0
    right = len(arr) - 1

while left <= right:
        mid = (left + right) // 2

if arr[mid] < X:
            return mid
        elif arr[mid] >= X:
            left = mid + 1

return -1

В этой реализации мы используем алгоритм бинарного поиска. Мы устанавливаем начальные значения для переменных `left` и `right` в крайние индексы массива. Затем мы выполняем итерации, пока `left` не станет больше `right`. В каждой итерации мы вычисляем средний индекс `mid` и сравниваем значение `arr[mid]` с X. Если `arr[mid]` меньше X, то мы возвращаем `mid`, так как это первый элемент, строго меньший X. Если `arr[mid]` больше или равно X, то мы обновляем значение `left` на `mid + 1` и продолжаем поиск в правой половине массива.

Если весь массив просмотрен и не найдено ни одного элемента, строго меньшего X, то функция возвращает -1.

Примечание: Данная реализация предполагает, что массив отсортирован по убыванию.

Источники: -(https://github.com/rezi100r/intro_algorithms) (репозиторий на GitHub с примерами алгоритмов) -(https://www.geeksforgeeks.org/binary-search/) (статья на GeeksforGeeks о бинарном поиске)