Advertisement
STANAANDREY

index of 1st 1 in infinte array

Dec 20th, 2021
1,191
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 0.80 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. int binarySrc(int arr[], int low, int high) {
  5.     int mid;
  6.     while (low <= high) {
  7.         mid = (low + high) / 2;
  8.         if (arr[mid] && (!mid || !arr[mid - 1])) {
  9.             break;
  10.         } else if (!arr[mid]) {
  11.             low = mid + 1;
  12.         } else {
  13.             high = mid - 1;
  14.         }
  15.     }
  16.     return mid;
  17. }
  18.  
  19. int posOfFi1(int arr[]) {
  20.     int low = 0, high = 1;
  21.     while (!arr[high]) {
  22.         low = high;
  23.         high *= 2;
  24.     }
  25.     return binarySrc(arr, low, high);
  26. }
  27.  
  28. int main() {
  29.     //simulate an infinite array
  30.     int arr[] = {
  31.         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  32.         1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
  33.         1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
  34.     };
  35.     printf("idx of 1st 1: %d", posOfFi1(arr));
  36.     return 0;
  37. }
  38.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement