在Python中以给定的单调序列查找元素位置

假设我们有一个数l和一个单调递增序列f(m)，其中f(m)= am + bm [log2(m)] + cm ^ 3和（a = 1，2，3，…），（b = 1，2，3，…），（c = 0，1，2，3，…）

这里[log2(m)]是以2为底的对数，并将该值四舍五入。所以，

如果m = 1，则值为0。

如果m = 2-3，则值为1。

如果m = 4-7，则值为2。

如果m = 8-15，则值为3。依此类推

我们必须找到值m，使f(m)= l，如果序列中不存在l，则必须打印0。我们必须牢记，值是以这样的方式表示的： 64位以及三个整数a，b和c小于或等于100。

因此，如果输入像a = 2，b = 1，c = 1，l = 12168587437017，则输出将为23001，因为f(23001)= 12168587437017

为了解决这个问题，我们将遵循以下步骤-

• SMALLER_VAL：= 1000000

• LARGER_VAL：= 1000000000000000

• 定义一个功能solve()。这将需要a，b，c，n

• 回答：= a * n

• lg_val：= n的日志基数2的下限

• ans：= ans + b * n * lg_val

• ans：= ans + c * n ^ 3

• 返回ans

• 从主要方法中，执行以下操作-

• 开始：= 1

• 结束：= SMALLER_VAL

• 如果c与0相同，则

• 结束：= LARGER_VAL

• 回答：= 0

• 在开始<=结束时，执行

• 开始：=中+ 1

• 结束：=中-1

• ans：=中

• 从循环中出来

• 中：=（开始+结束）/ 2（仅取整数部分）

• val：= solve(a,b,c,mid)

• 如果val与k相同，则

• 否则当val> k时

• 除此以外，

• 返回ans

示例

让我们看下面的实现以更好地理解-

from math import log2, floor
SMALLER_VAL = 1000000
LARGER_VAL = 1000000000000000
def solve(a, b, c, n) :
   ans = a * n
   lg_val = floor(log2(n))
   ans += b * n * lg_val
   ans += c * n**3
   return ans
def get_pos(a, b, c, k) :
   begin = 1
   end = SMALLER_VAL
   if (c == 0) :
      end = LARGER_VAL
   ans = 0
   while (begin <= end) :
      mid = (begin + end) // 2
      val = solve(a, b, c, mid)
      if (val == k) :
         ans = mid
         break
      elif (val > k) :
         end = mid - 1
      else :
         begin = mid + 1
   return ans
a = 2
b = 1
c = 1
k = 12168587437017
print(get_pos(a, b, c, k))

输入项

2,1,1,12168587437017

输出结果

23001