Java 通过二分查找法找到一个数的平方根

一个数的平方根是一个整数值，当与自身相乘时得到原始数。在本文中，我们将编写一个使用二分查找法来找到一个数的平方根的Java程序。找到一个数的平方根是二分查找算法的一个应用。我们将在本文中详细讨论如何使用二分查找法计算平方根。

示例：

Input: 64 
Output: 8

因为64的平方根是8，所以输出为8。

Input: 16
Output: 4

因为16的平方根是4，所以输出为4。

二分查找

二分查找是一种用于在排序数组中找到元素（即键值）的算法。二分算法的工作方式如下 –

假设数组为’arr’。对数组进行升序或降序排序。
初始化low = 0，high = n-1（n为元素的数量），并计算middle = low + (high-low)/2。如果arr[middle] == key，则返回middle即数组的中间索引。
否则，如果键值小于arr[middle]元素，则将high索引设置为middle索引-1，或者如果键值大于middle元素，则将low索引设置为middle索引+1。
继续进行二分查找，直到找到需要找到的元素。
如果low大于high，则直接返回false，因为键值不在数组’arr’中。

使用二分查找找到键值的示例

问题 - 给定一个排序的整数数组arr = [1, 3, 5, 7, 9, 11]，使用二分查找找到元素（键值）7的索引。

解决方案

初始化low = 0，high = 5（数组的最后一个索引）。
while循环的第一次迭代给出了中间索引mid = low + (high-low)/2。
mid = 0 + (5-0)/2 = 2。
arr[mid]的值是5，小于键值7。因此，我们更新low = mid + 1 = 3。
while循环的第二次迭代通过使用low + (high-low)/2来给出中间索引mid = 4。
arr[mid]的值是9，大于键值7。因此，我们更新high = 3（mid – 1）。
while循环的第三次迭代给出了中间索引mid = 3。
arr[mid]的值是7，等于键值。因此，我们返回中间索引，即3。

因此，在给定的数组中，键值7的索引为3，这是我们使用二分查找算法找到的。

使用二分查找找到平方根的算法

考虑一个数字’n’，并初始化low=0和right=n(给定的数字)。
使用mid = low + (high-low)/2找到low和high的中间值。
找到mid * mid的值，如果mid * mid == n，则返回mid的值。
如果mid的值小于n，则low=mid+1，否则high=mid-1。
重复步骤2到4，直到找到该值。

示例1：使用二分查找

在这个示例中，我们创建一个自定义类’BinarySearchSqrt’，并在’sqrt’函数中实现用于找到一个数字平方根的二分查找代码。现在，创建自定义类对象，并使用一个整数数字初始化一个名为’number’的变量，并使用类对象调用’sqrt’函数，从而显示所需的输出。

//Java Program to find Square root of a number using Binary Search
import java.util.*;
class BinarySearchSqrt {
   public  int sqrt(int number) {
      int low = 0;
      int high = number;
      while (low <= high) {
         int mid = (low + high) / 2;
         int square = mid * mid;
         if (square == number) {
            return mid;
         } else if (square < number) {
            low = mid + 1;
         } else {
            high = mid - 1;
         }
      }
      return 0;
   }
}
public class Main {
   public static void main(String[] args) {
      int n = 64;
      BinarySearchSqrt Obj  = new  BinarySearchSqrt();
      int result= Obj.sqrt(n);
      System.out.println("Square root of " + n + " = " + result);
   }
}

输出

Square root of 64 = 8

时间复杂度：O(NlogN) 辅助空间：O(1)

示例2：使用二分查找和Math.pow()

在下面的示例中，我们创建了一个自定义类’BinarySearchSqrt’，并实现了二分查找代码以找到’sqrt’函数中一个数字的平方根代码。’sqrt’函数使用内置函数’Math.pow()’来计算一个数字的平方。现在，创建自定义类对象并初始化一个名为’number’的整数变量，并使用该类对象调用’sqrt’函数，从而显示所需的输出。

//Java Program to find Square root of a number using Binary Search and Math.pow()
import java.util.*;
class BinarySearchSqrt {
   public  int sqrt(int number) {
      int low = 0;
      int high = number;
      while (low <= high) {
         int mid = (low + high) / 2;
         if (Math.pow(mid,2) == number) {
            return mid;
         } else if (Math.pow(mid,2) < number) {
            low = mid + 1;
         } else {
            high = mid - 1;
         }
      }
      return 0;
   }
}
public class Main {
   public static void main(String[] args) {
      int n = 64;
      BinarySearchSqrt Obj  = new  BinarySearchSqrt();
      int result= Obj.sqrt(n);
      System.out.println("Square root of " + n + " = " + result);
   }
}