Propose a binary search algorithm, 𝐵𝐵, that decides the perfect square problem.
Question
Propose a binary search algorithm, 𝐵𝐵, that decides the perfect square problem.
Solution
Sure, here is a simple binary search algorithm in Python that can be used to solve the perfect square problem:
def is_perfect_square(n):
if n < 2:
return True
left, right = 2, n // 2
while left <= right:
mid = left + (right - left) // 2
guess_squared = mid * mid
if guess_squared == n:
return True
elif guess_squared > n:
right = mid - 1
else:
left = mid + 1
return False
This algorithm works by repeatedly dividing the search space in half. If the square of the midpoint is equal to the input number, then we know that the number is a perfect square. If the square of the midpoint is greater than the input number, then we know that the square root of the number must be less than the midpoint, so we update the right boundary of our search space to be the midpoint minus one. If the square of the midpoint is less than the input number, then we know that the square root of the number must be greater than the midpoint, so we update the left boundary of our search space to be the midpoint plus one. We continue this process until we have found the square root of the number or until our search space is empty. If our search space is empty, then the number is not a perfect square.
Similar Questions
The least integer than must be added to(9798 × 9792) to make it perfect square is
Which of the following can be a perfect square?*(a) 81458(b) 52912(c) 19853(d) 11025
Mary is working to find the square root of a number in C++ language using a binary search algorithm. Which of the following options can she perform to get an optimized solution?Constraints0<=x<=2^31-1Optionsint fun(int x) { if(x==1) return x; int low=0,high=x; int res=0; while(low<high){ int mid=(low+high)/2; if(mid>x/mid) high=mid; else{ res=mid; low=mid+1; } } return res;}int fun(int x) { if(x==1) return x; int low=0,high=x; int res=0; while(low<=high){ int mid=low+(high-low)/2; if(mid>x/(mid*mid) high=mid; else{ res=mid; low=mid+1; } } return res;}int fun(int x) { if(x==1) return x; int low=0,high=x; int res=0; while(low<high){ int mid=low+(high-low)/2; else if((mid*mid*mid)>x) high=mid; else{ res=mid; low=mid+1; } } return res;}int fun(int x) { int res=0; for(int i=0;i<=x;i++){ if((i*i)<=x) res=i; } return res;}
Which of the following is not a perfect square number?12252025252530254225
Which of the following numbers is a perfect square?a209 b1 000c1 524 d1 764
Upgrade your grade with Knowee
Get personalized homework help. Review tough concepts in more detail, or go deeper into your topic by exploring other relevant questions.