乐趣区

关于golang:Golang力扣Leetcode-367-有效的完全平方数二分查找

题目 :给定一个 正整数 num,编写一个函数,如果 num 是一个齐全平方数,则返回 true,否则返回 false。

进阶:不要 应用任何内置的库函数,如 sqrt

链接:力扣 Leetcode – 367. 无效的齐全平方数.

示例 1:

输出:num = 16
输入:true

示例 2:

输出:num = 14
输入:false

思路 :应用 二分查找 解决问题。因为 num 是正整数,所以若正整数 x 满足 x*x=num,则 x 肯定满足 1≤x≤num。于是咱们能够将 1 和 num 作为二分查找搜寻区间的初始边界。
          因为咱们在挪动左侧边界 left 和右侧边界 right 时,新的搜寻区间都不会蕴含被查看的下标 mid,所以搜寻区间的边界始终是咱们没有查看过的。因而,当 left = right 时,咱们仍须要查看 mid=(left+right)/2。

  • 如果 mid*mid=num,则下标 mid 即为要寻找的下标,返回 true;
  • 如果 mid*mid<num,则 left=mid+1;
  • 如果 mid*mid>num,则 right=mid-1。

Go 代码:

package main

import "fmt"

func isPerfectSquare(num int) bool {
    left := 0
    right := num
    for left <= right {mid := (left + right) / 2
        if mid*mid == num {return true} else if mid*mid < num {left = mid + 1} else {right = mid - 1}
    }
    return false
}
func main() {fmt.Println(isPerfectSquare(15))
}

提交截图

退出移动版