整数平方根判定程序效率评估及优化建议咨询

我是编程新手，出于兴趣编写了一款判定整数是否存在整数平方根的程序，结合末尾数字校验、二分查找等方式缩小搜索范围。程序代码如下：

def endingTest (num):
  print ("Now checking the input for ending that won't have integer roots")
  print ()
  endCheck = str(num)
  lastDigit = endCheck[-1]
  noIntegerSquareEnding = ["2", "3", "7", "8"]
  for digit in noIntegerSquareEnding:
    if lastDigit in noIntegerSquareEnding:
      print ("The input ends in",lastDigit,"which can't have any integer roots")
      print ("Number ending check is done \n")
      print ("No integer root found.")
      return False
    else:
      print ("Input does not end in 2, 3, 7, 8")
      print ("Input ending check is done")
      print ()
      return True
      
def binarySearch (num):    
  print ("Now checking for the range where integer root could be found")
  digits = str(num)
  count = 0
  for digit in digits:
    count += 1
  ceiling = 10**((count/2))
  floor = 10**((count/2)-1)
  high = int(ceiling)
  low = int(floor)
  print ("starting search range is between", low,"and",high)
  while high-low>10:
    mid = (low+high)//2
    if mid**2 == num:
      print ("Integer root found: ", mid, "\n")
      print (steps)
      return [False, None, None]
    elif mid**2 > num:
      high = mid
    elif mid**2 < num:
      low = mid
  print ()
  print ("Binary search is done. Search range is narrowed down to between", low, "and", high)
  return [True, low, high]

def squareTest (num, low, high):
  print ("Begin squaring every number from", low, "to", high)
  print ()
  for i in range (low, high+1):
    if i**2 == num:
      print ("Integer root found: ", i)
      return
    
    elif i**2 > num and i < high:
      print ("The root",i,"already produces a square of",i**2, "which is higher than", num)
      print ("All values from", i+1, "to", high,"are definitely out of range and therefore skipped")
      print ()
      print ("No integer root found")
      return
    
    elif i**2 < num and i < high:
      pass
    
    else:
      print ("No integer root found")
      return
      
    

def userInput ():
  try:
    userNumber = int(input("Enter an integer to find its integer root: "))
  except:
    print("That is an invalid entry. Try again.")
    return None, True
  else:
    print ("-----------------------------")
    return userNumber, False

def findIntegerRoot(testVal):
  print ("Searching for integer root of", testVal)
  print ("-----------------------------")
  if testVal < 100:
    print ("Because the number is really small, we will try squaring numbers to find root.\n")
    print ("If", testVal, "has an integer square root, it would fall between 0 and half of", testVal, "plus 1\n")
    squareTest (testVal, 1, (testVal//2)+1)
    return
  if endingTest(testVal) == False:
    return
  if testVal <= 2500:
    print ("Because the number is relatively small, we believe it's more efficient to skip binary search step.\n")
    print ("If", testVal, "has an integer square root, it would fall between 0 and half of", testVal, "plus 1\n")
    squareTest (testVal, 1, (testVal//2)+1)
    return
  proceed = binarySearch(testVal)
  if proceed[0] == False:
    return
  high = proceed[2]
  low = proceed[1]
  squareTest (testVal, low, high)
  

def main():
  repeat = True
  while repeat == True:
    testVal, repeat = userInput()
  findIntegerRoot(testVal)
  print ("----------------------------")
  print ("End of integer root search. \n")
  

main()

我不确定该程序在步骤数量与资源占用方面是否达到高效标准（高效指用最少步骤和资源得出结果），恳请专业反馈。

效率问题分析与优化建议 #

现有实现的低效点 #

• 末尾校验逻辑冗余：endingTest里用循环遍历禁止数字列表，但直接判断lastDigit in noIntegerSquareEnding即可，循环完全多余；而且转字符串取最后一位的效率不如用数学运算num % 10。
• 二分查找不彻底：当前二分循环在high-low>10时就终止，切换到线性搜索，浪费了二分查找O(log n)的高效特性，反而引入O(n)的线性遍历步骤。
• 初始范围计算粗糙：通过数字位数计算上下界的方式，不如直接用num//2作为初始上界（num>2时）精准，会导致二分查找需要更多迭代次数；另外binarySearch里的steps变量未定义，运行会报错。
• 小数字处理范围不合理：对<=2500的数字用(testVal//2)+1作为上界，比如2500的平方根是50，但这个上界是1251，线性搜索范围被无端放大，完全没必要。
• 冗余IO操作：过多的打印语句会增加IO开销，对于追求高效的程序来说，非必要的输出应该尽量减少。

优化核心方向 #

1. 简化末尾校验：用数学运算取最后一位，直接判断是否在禁止列表，去掉冗余循环。
2. 完整二分查找：全程用二分查找完成搜索，直到找到平方根或确定不存在，避免切换线性搜索。
3. 精准范围控制：设置更合理的初始上下界，减少二分迭代次数。
4. 处理特殊值：提前处理0、1、负数等特殊情况，避免无效计算。
5. 精简冗余逻辑：合并重复的小数字处理分支，去除不必要的打印。

优化示例代码 #

def ending_test(num):
    last_digit = num % 10
    forbidden_digits = {2, 3, 7, 8}
    return last_digit not in forbidden_digits

def binary_search_sqrt(num):
    if num == 0 or num == 1:
        return num
    low = 1
    high = num // 2
    while low <= high:
        mid = (low + high) // 2
        mid_sq = mid * mid
        if mid_sq == num:
            return mid
        elif mid_sq < num:
            low = mid + 1
        else:
            high = mid - 1
    return None

def find_integer_root(test_val):
    if test_val < 0:
        print("负数没有整数平方根")
        return
    if not ending_test(test_val):
        print(f"输入数字末尾是{test_val%10}，不存在整数平方根")
        return
    root = binary_search_sqrt(test_val)
    if root:
        print(f"整数平方根为: {root}")
    else:
        print("不存在整数平方根")

def user_input():
    while True:
        try:
            return int(input("请输入一个整数来查找其整数平方根: "))
        except ValueError:
            print("输入无效，请重新输入。")

def main():
    test_val = user_input()
    print("-----------------------------")
    find_integer_root(test_val)
    print("----------------------------")
    print("整数平方根搜索结束。")

if __name__ == "__main__":
    main()

优化后的效率提升 #

• 时间复杂度优化：从原程序的混合O(log n)+O(n)，彻底降到O(log n)，步骤数大幅减少。
• 减少不必要计算：去掉字符串转换、冗余循环和无效范围遍历，降低资源占用。
• 避免错误：修复了原程序中steps变量未定义的问题，同时增加了特殊值处理，鲁棒性更强。

内容的提问来源于stack exchange，提问作者Timothy Chang