?

題目：搜索

（1）請寫出Java代碼，實現二分搜索（給定一個按升序排列的數組和一個要查找的值，返回該值在數組中的index）

（2）說明該算法時間復雜度

（3）如果改成三分搜索，時間復雜度將會是多少？說明與二分搜索相比較是提升還是降低。

解答：

（1）

package ddd; /*** @author George* @description ? 二分搜索* 算法要求：* 1.必須采用順序存儲結構。* 2.必須按關鍵字大小有序排列。**/ public class BinarySearch {public static void main(String[] args) {int[] nums = {1,2,3,4,5,6,7,8,9};System.out.println(search(nums, 2));}public static int search(int[] nums,int key){//定義初始最小、最大索引int start = 0;int end = nums.length - 1;//確保不會出現重復查找，越界while (start <= end) {//計算出中間索引值int middle = (end + start)>>>1 ;//防止溢出if (key == nums[middle]) {return middle;//判斷下限} else if (key < nums[middle]) {end = middle - 1;//判斷上限} else {start = middle + 1;}}//若沒有，則返回-1return -1;} }

（2）二分查找的基本思想是將n個元素分成大致相等的兩部分，取a[n/2]與x做比較，如果x=a[n/2],則找到x,算法中止；如果x<a[n/2],則只要在數組a的左半部分繼續搜索x,如果x>a[n/2],則只要在數組a的右半部搜索x.

時間復雜度無非就是while循環的次數！

總共有n個元素，

漸漸跟下去就是n,n/2,n/4,....n/2^k（接下來操作元素的剩余個數），其中k就是循環的次數

由于你n/2^k取整后>=1

即令n/2^k=1

可得k=log2n,（是以2為底，n的對數）

所以時間復雜度可以表示O(h)=O(log2n)

（3）

首先二分查找的時間復雜度：因為每次都是折半，可以構造一顆遞歸樹，共log2(n)層，每層只需O(1)的時間。所以共花費O(1)*log2(n)=O(log2(n))時間。

其次三分查找，也可類似構造一個遞歸樹，共log3(n)層，而每層需要比較的次數為2，所以時間復雜度為O(2log3(n))。

最后求得使 2log3(n)>log2(n) 對n>0始終成立。所以三分查找比二分查找的性能就是差。

當然對于二分查找的缺陷分析，優點：大大提高了查找的效率， 缺陷：只能查找單調遞增的序列。

對于假若要查找一個拋物線的最值的時候，這里是二分法是不適用的，這里適用三分。

總結

以上是生活随笔為你收集整理的大剑无锋之二分搜索、二分搜索时间复杂度、三分查找呢？的全部內容，希望文章能夠幫你解決所遇到的問題。

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