資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究使用二分查詢法查詢數字平方根的 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]，使用二分查詢法查詢元素（即鍵）key = 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 迴圈的第二次迭代為我們提供了中間索引 mid = 4，使用 low+ (high-low)/2。
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);
}
}
輸出
Square root of 64 = 8
時間複雜度：O(NlogN) 輔助空間：O(1)
因此，在本文中，我們討論瞭如何在 Java 中使用二分查詢演算法查詢數字的平方根。
2K+ 瀏覽量
