Module: Algorithmable::Cups::NumberOfOccurrencesInArray

Includes:
Searches
Defined in:
lib/algorithmable/cups/number_of_occurrences_in_array.rb

Instance Method Summary collapse

Methods included from Searches

#binary_search, #new_binary_search_tree

Instance Method Details

#find_first_one(collection, low, high, target) ⇒ Object 



20
21
22
23
24
25
26
27
28
29
30
31
32
 
# File 'lib/algorithmable/cups/number_of_occurrences_in_array.rb', line 20

def find_first_one(collection, low, high, target)
  #   if(high >= low)
  #   {
  #     int mid = (low + high)/2;  /*low + (high - low)/2;*/
  #     if( ( mid == 0 || x > arr[mid-1]) && arr[mid] == x)
  #       return mid;
  #     else if(x > arr[mid])
  #       return first(arr, (mid + 1), high, x, n);
  #     else
  #       return first(arr, low, (mid -1), x, n);
  #   }
  #   return -1
end

#find_last_one(collection, low, high, target) ⇒ Object 



34
35
36
37
38
39
40
41
42
43
44
45
46
 
# File 'lib/algorithmable/cups/number_of_occurrences_in_array.rb', line 34

def find_last_one(collection, low, high, target)
  # if(high >= low)
  #   {
  #     int mid = (low + high)/2;  /*low + (high - low)/2;*/
  #     if( ( mid == n-1 || x < arr[mid+1]) && arr[mid] == x )
  #       return mid;
  #     else if(x < arr[mid])
  #       return last(arr, low, (mid -1), x, n);
  #     else
  #       return last(arr, (mid + 1), high, x, n);
  #   }
  #   return -1;
end

#linear_solve(collection, target) ⇒ Object 



6
7
8
9
10
11
12
 
# File 'lib/algorithmable/cups/number_of_occurrences_in_array.rb', line 6

def linear_solve(collection, target)
  result = Hash.new 0
  collection.each do |item|
    result[item] += 1
  end
  result[target]
end

#logarithmic(collection, target) ⇒ Object 



14
15
16
17
18
 
# File 'lib/algorithmable/cups/number_of_occurrences_in_array.rb', line 14

def logarithmic(collection, target)
  i = find_first_one collection, 0, collection.size - 1, target
  j = find_last_one collection, i, collection.size - 1, target
  j - i + 1
end