LeetCode： Valid Perfect Square

Question

Given a positive integer num, write a function which returns True if num is a perfect square else False.

Follow up: Do not use any built-in library function such as sqrt.

Example 1:

Input: num = 16

Output: true

Example 2:

Input: num = 14

Output: false

Solution

這裡可以利用 binary search (二分搜索法) 的技巧來解題。 其概念是取輸入值(num)的ㄧ半為動態的比對值(mid)，然後左半部為 1，右半部的最大值為輸入值(num)。 如果 mid 的平方剛好等於輸入值的平方就回傳 true，代表 num 是完全平方數。

但如果 mid 的平方值大於 num，則代表 mid 的值可以降低一點(right = mid - 1)。 同樣地，如果 mid 的平方值小於 num，則代表 mid 的值可以提高一點(left = mid + 1)。當最後 while 迴圈跑完，沒有比對成功就代表此輸入值(num)不是完全平方數。

def is_perfect_square(num)
  left = 1
  right = num

  while left <= right
    mid = (left+right)/2
    temp = mid * mid
    if temp == num
      return true
    elsif temp > num
      right = mid - 1
    else
      left = mid + 1
    end
  end
  return false
end

Explanation #1

以 Example 1 來說

Input: nums = 16
第一圈
left = 1
right = 16
while 1 <= 16
  mid = 8
  temp = 84
  if 64 == 18
    # won't enter here
  elsif (64) > 18
    right = (8-1)
  else (64) < 9
    # won't enter here
  end
end

第二圈
while 3 <= 5
  mid = (1+8)/2
  temp = 4 * 4
  if 16 == 16
    return true
  elsif
    # won't enter here
  else
    # won't enter here
  end
end