二分查找：

數據需要是順序表（數組）

數據必須有序

可以一次排序，多次查找；如果數據頻繁插入，刪除操作，就必須保證每次操作后有序，或者查找前繼續排序，這樣成本高，二分查找不合適

數據太小，不用二分查找，直接遍歷

數據太大，也不用，因為數組需要連續的內存，存儲數據比較吃力

復雜度 lg₂n

題目： 求一個數的平方根

• 例如：二分法求根號5

  a:折半： 5/2=2.5

  b:平方校驗： 2.5*2.5=6.25>5，并且得到當前上限2.5

  c:再次向下折半：2.5/2=1.25

  d:平方校驗：1.25*1.25=1.5625<5,得到當前下限1.25

  e:再次折半：2.5-(2.5-1.25)/2=1.875

  f:平方校驗：1.875*1.875=3.515625<5,得到當前下限1.875

循環求解：

#include<iostream> double rootbinarysearch(double num) {if(num == 1)return 1;double lower = 1, upper = num, curValue;if(lower > upper)std::swap(lower,upper);while(upper-lower > 0.00000001){curValue = lower+(upper-lower)/2;if(curValue*curValue < num)lower = curValue;elseupper = curValue;}return curValue; }int main() {double x;std::cin >> x;std::cout << x << "的平方根是 " << rootbinarysearch(x);return 0; }

遞歸求解：

/*** @description: 求根號n，遞歸法* @author: michael ming* @date: 2019/4/15 23:05* @modified by: */ #include <iostream> double rootbinarysearch_R(double num, double upper, double lower) {if(num == 1)return 1;if(lower > upper)std::swap(lower,upper);double curValue = lower+(upper-lower)/2;if(upper-lower < 0.00000001)return curValue;if(curValue*curValue < num)return rootbinarysearch_R(num,curValue,upper);elsereturn rootbinarysearch_R(num,lower,curValue); }int main() {double x;std::cin >> x;std::cout << x << "的平方根是 " << rootbinarysearch_R(x,x,1);return 0; }

總結

以上是生活随笔為你收集整理的算法--二分查找--求平方根（循环法/递归法）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。