There is an array of 1 and 0, the size of N

 1 1 1 1 1 0 0 0 0 0 0

It is necessary for logN determine the place on which is the rightmost (last unit). If there are no units at all, output -1 .

A binary search came to mind:
- if we hit zero, go left
- if the unit is trying to expand, going to the right

But there were problems with writing code (((

  • There is a standard algorithm std :: lower_bound, which you can use to search for 0 or std :: upper_bound which you can use to search 1 - Vlad from Moscow
  • An array of just such - first one, then zeros? - Harry
  • Well, they themselves write - a dichotomy. Two variables: the beginning, the end, choose the middle, check, narrow the range. Repeat until the range is greater than one. - vp_arth
  • Yes array, just like that! - Roman Alexandrovich
  • And how to narrow the range and what is the exit condition? - Roman Alexandrovich

2 answers 2

You can use either the standard std::upper_bound algorithm using 1 as an argument, or the std::lower_bound algorithm using 0 as an argument.

For example,

 #include <iostream> #include <functional> #include <iterator> #include <algorithm> int main() { int a[] = { 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, }; auto it = std::upper_bound(std::begin(a), std::end(a), 1, std::greater<int>()); if (it != std::begin(a)) { std::cout << "The last 1 is at the position " << std::distance(std::begin(a), std::prev(it)) << std::endl; } else { std::cout << "There is no 1 in the array" << std::endl; } }

Output of the program to the console

 The last 1 is at the position 4

Instead of expression

 std::distance(std::begin(a), std::prev(it))

you can use the expression

 std::distance(std::begin(a), it) - 1

And then you get the desired position if 1 is present in the array or -1 if there is none 1.

  • std algorithms guaranteed O (log N)? - DNS
  • @DNS Yes, using binary search. - Vlad from Moscow

Instead of pseudo-code I will give javascript

 function search(arr) { // стартовый диапазон let start = 0, end = arr.length; do { // середина let middle = Math.floor((end-start)/2)+start; if (arr[middle] == 1) { start = middle; // обрезаем половину со старта } else { end = middle; // обрезаем половину с хвоста } } while(end - start > 1); // остался один элемент return arr[start] == 1 ? start : -1; // нашли? } console.log(search([1,1,1,0,0,0,0,0])); // 2 console.log(search([1,1,1,1,1,0,0,0])); // 4 console.log(search([1,0,0,0,0,0,0,0])); // 0 console.log(search([0,0,0,0,0,0,0,0])); // -1