資訊工程 - 演算法與資料結構 - 資料結構 - 搜尋演算法（Search Algorithm）
上一篇：資訊工程 - 演算法與資料結構 - 資料結構 - 時間複雜度（Time Complexity）
線性搜索（Linear Search）
這是最簡單的搜索方法，原理就是給你一堆數字，你要找某個數的話，直接按順序一個一個找。
寫法的話，有3個形參，分別是 陣列，陣列的大小，值。
你需要寫一個最簡單的for循環和if進行判斷。
代碼：
int linear_search(int nums[],int n,int val)
{
int i;
for(i=0;i<n;i++)
if(nums[i]==val)
return i;
return -1;
}
二分搜尋（Binary Search）
這個，必須是用排列好的數據，再進行二分探索。（最好是從小到大排列）
不管你是用遞歸還是循環，本質是不變的。
使用遞迴函數的二分搜尋演算法：
int _binary_search(int nums[],int l,int r,int x)
{
if(r>=l)
{
int mid=(l+r)/2;
if(nums[mid]==x)
return mid;
else if(nums[mid]>x)
return _binary_search(nums,l,mid-l,x);
else
return _binary_search(nums,mid+1,r,x);
}
return -1;
}
int binary_search(int nums[], int n, int x)
{
return _binary_search(nums,0,n-1,x);
}
使用循環的二分搜尋演算法：
int binary_search(int nums[],int n,int x)
{
int l=0,r=n-1;
while(l<=r)
{
int mid=(l+r)/2;
if(nums[mid]==x)
return mid;
else if(nums[mid]>x)
r=mid-1;
else
l=mid+1;
}
return -1;
}
使用特殊資料構造的探尋演算法
二分搜尋法是基於排序完畢的數列進行的。下一張將介紹二元搜尋樹和資料結構。
二元搜尋樹，用O(log(n))的計算量能探索。接下來將介紹如何用Hash table以O(1)的計算量的探索。
留言
張貼留言