• # Perfect Squares and ℤ/ℝ Square Roots

This post will explore how the binary search algorithm can help us check if a given number is a perfect square, find the integer square root of a given number, and find the real square root of a given number efficiently relative to linear search.

## Perfect Squares

A perfect square is a number that can be expressed as the product of two equal integers. For example, the numbers 4, 9, and 121 are perfect squares because they are the products of 22, 32, and 112 respectively.

### Example

``````#   Current Search Range    m
#   1       5       9
#   i       m       j       1 + (9 - 1)/2 = 5
#   1       2       4
#   i       m       j       1 + (4 - 1)/2 = 2
#   3               4
#   im              j       3 + (4 - 3)/2 = 3
#   done because 3 * 3 = 9
#   return m``````

### Implementation

``````public static boolean isPerfectSquare(int x) {
int i = 1, j = x;

while (i <= j) {
int m = i + (j - i)/2;
int p = m * m;

if (p == x)
return true;
else if (p < x)
i = m + 1;
else
j = m - 1;
}

return false;
}``````

## ℤ Square Root

This problem concerns with finding the integer portion of the square root of a number. For example, when given 1, 2, or 3, this function should return 1 because the square roots of these numbers are 1, 1.414, and 1.732 respectively, but the integer portion of these numbers is 1. To further illustrate the example, when given 4, 5, or 7, this function should return 2 because the square roots of these numbers are 2, 2.236, and 2.646 respectively, but the integer portion of these numbers is 2.

### Example

``````#   Current Search Range    m
#   1       4       7
#   i       m       j       1 + (7 - 1)/2 = 4
#   1       2       3
#   i       m       j       1 + (4 - 1)/2 = 2
#   2               3
#   im              j       2 + (3 - 2)/2 = 2
#   3
#   imj                     3 + (3 - 3)/2 = 3
#   done because j < i
#   return i - 1``````

### Implementation

``````public static int intSqrt(int x) {
int i = 1, j = x;

while (i <= j) {
int m = i + (j - i)/2;
int p = m * m;

if (p <= x)
i = m + 1;
else
j = m - 1;
}

return i - 1;
}``````

An observation worth noting is that the range covered by an integer square root increases as the given value increases.

### Observation

``````#   Range                   ℤ Square Root   Count
#   0                       0               1
#   1   2   3               1               3
#   4   5   6   7   8       2               5
#   9   10  11  ... 15      3               7``````

## ℝ Square Root

This problem concerns with finding the real square root of a given number up to a given tolerance. It should be noted that this is not the implementation of the Java standard library square root function. The following example traces out the square root of 5 with tolerance of 0.01, which is 2.24.

### Example

``````#   x = 5.0
#   EPSILON (E) = 0.01
#
#   Current Search Range    Condition           m
#   1.00    3.00    5.00
#   i       m       j       1.00 < 5.00(1 - E)  1.00 + 0.5(5.00 - 1.00)
#   1.00    2.00    3.00
#   i       m       j       1.00 < 3.00(1 - E)  1.00 + 0.5(3.00 - 1.00)
#   2.00    2.50    3.00
#   i       m       j       2.00 < 3.00(1 - E)  2.00 + 0.5(3.00 - 2.00)
#   2.00    2.25    2.50
#   i       m       j       2.00 < 2.50(1 - E)  2.00 + 0.5(2.50 - 2.00)
#   2.00    2.13    2.25
#   i       m       j       2.00 < 2.25(1 - E)  2.00 + 0.5(2.25 - 2.00)
#   2.13    2.19    2.25
#   i       m       j       2.13 < 2.25(1 - E)  2.13 + 0.5(2.25 - 2.13)
#   2.19    2.22    2.25
#   i       m       j       2.19 < 2.25(1 - E)  2.19 + 0.5(2.25 - 2.19)
#   2.22    2.24    2.25
#   i       m       j       2.22 < 2.25(1 - E)  2.22 + 0.5(2.25 - 2.22)
#   2.24            2.25
#   i               j
#   done because 2.24 < 2.25(1 - E) is false
#   return i``````

### Implementation

``````public static double realSqrt(double x) {
double i, j;
if (x < 1.0) {
i = x;
j = 1.0;
}
else {
i  = 1.0;
j = x;
}

final double EPSILON = 0.00001;

while (i <= j * (1 - EPSILON)) {
double m = i + 0.5 * (j - i);
double p = m * m;

if (p == x)
return m;
else if (p < x)
i = m;
else
j = m;
}

return i;
}``````
• ## BinarySearch in JAVA

When given a sorted list of numbers, binary search is the best algorithm to have in your arsenal. The binary search finds the target element in O(log(n)) time by taking adv...

• ## SelectionSort in JAVA

Today, I will be show another comparative sorting algorithm known as Selection Sort. Selection sort works by finding a smaller element downstream from the current element a...

• ## BinaryTree PreOrder Traversal in JAVA

PreOrder traversal is very similar to in-order traversal in terms of code. The idea behind pre-order traversal is to do all the processing before visiting the left subtree ...

• ## Next Greater Element in Linear Time in JAVA

This is my implementation of the algorithm for that gets the next greater element than the current element in linear time. For elements with no next greater element, match ...

• ## BinaryTree VerticalOrder Traversal in JAVA

This is my implementation of the BinaryTree vertical order traversal. Vertical order traversal is an algorithm that groups all nodes with the same horizontal distance toget...

• ## Check if Array is in BST PreOrder Form in JAVA

This is my recursive implementation of the algorithm that checks if a given Array is in BinarySearchTree PreOrder form. The idea behind this algorithm is to start with the ...

• ## BinaryTree Maximum Sum Path in JAVA

This is my implementation of the algorithm on finding the maximum sum path of a BinaryTree. The path does not have to start from the root node and does not have to end on a...

• ## BinaryTree InOrder Traversal in JAVA

This is my iterative and recursive implementation of the InOrder traversal method on a BinaryTree data structure. InOrder traversal is a form of depth first traversal, so I...

• ## InsertionSort in JAVA

Insertion sort is a simple comparison sorting algorithm that uses two pointers to reorder a set of unsorted numbers. Suppose there is a set of unsorted numbers. If the set ...

• ## Heap Implementation in JAVA

This is my Java implementation of the Heap data structure. The Heap data structure is also known as the PriorityQueue in the Java standard library. It is a binary tree that...

• ## Queue Implementation in JAVA

This is my Java implementation of the Queue data structure. It exhibits the first in first out property, which is useful in applications such as breadth first traversal and...

• ## Separate Chaining HashTable Implementation in JAVA

This is my Java implementation of the HashTable data structure with Separate Chaining as collision correction. Collision is minimized when the table size (threshold) is ini...

• ## MergeSort on LinkedList in JAVA

I decided to implement the MergeSort. LinkedList is preferred for MergeSort over an Array because it does not require a lot of random access, and a LinkedList does not requ...

• ## Trie Implementation in JAVA

This is my Java implementation of the Trie data structure using the Java sorted map data structure, TreeMap, in the TrieNode class. I am using the TreeMap DS instead of the...