⑴ c語言編程實現「折半查找」的過程。
//參考代碼如下：
#include <stdio.h>
int main()
{
int i, j, n, k=0, isFound=0;
int num[15] = {88,86,75,74,61,56,52,43,39,34,31,22,18,16,8}; //測試數組
printf("請輸出一個整數：\n");
scanf("%d", &n);
i = (int)15/2; //對折位移量
j = (int)15/2; //取數「指針」
while(k<2)
{
i = (int)i/2;
if(i == 0) k++; //i==0 即折半到無可再折時，仍有最後一次比較，故以k做計數
//若未相等，計算下一循環指針的位置
if(n<num[j])
j = j + (i + 1);
else if(n>num[j])
j = j - (i + 1);
else
{
isFound = 1;
break; //若找到相等數，標記已找到並退出循環
}
}
//輸出結果
if(isFound)
printf("該數是數組中第%d個元素的值\n", j);
else
printf("查無此數！\n");
return 0;
}
python實現折半查找和歸並排序演算法
今天依舊是學演算法，前幾天在搞bbs項目，界面也很醜，評論功能好像也有BUG。現在不搞了，得學下演算法和數據結構，筆試過不了，連面試的機會都沒有……
今天學了折半查找演算法，折半查找是蠻簡單的，但是歸並排序我就挺懵比，看教材C語言寫的歸並排序看不懂，後來參考了別人的博客，終於搞懂了。
折半查找
先看下課本對於 折半查找的講解。注意了，折半查找是對於有序序列而言的。每次折半，則查找區間大約縮小一半。low,high分別為查找區間的第一個下標與最後一個下標。出現low>high時，說明目標關鍵字在整個有序序列中不存在，查找失敗。
看我用python編程實現:
defBinSearch(array, key, low, high): mid=int((low+high)/2) ifkey==array[mid]:# 若找到 returnarray[mid] iflow > high: returnFalse ifkey < array[mid]: returnBinSearch(array, key, low, mid-1)#遞歸 ifkey > array[mid]: returnBinSearch(array, key, mid+1, high) if__name__=="__main__": array=[4,13,27,38,49,49,55,65,76,97] ret=BinSearch(array,76,0,len(array)-1)# 通過折半查找，找到65 print(ret)
輸出: 在列表中查找76.
76
時間復雜度：O(logn)
歸並排序演算法
先闡述一下排序思路：
首先歸並排序使用了二分法，歸根到底的思想還是分而治之。歸並排序是指把無序的待排序序列分解成若干個有序子序列，並把有序子序列合並為整體有序序列的過程。長度為1的序列是有序的。因此當分解得到的子序列長度大於1時，應繼續分解，直到長度為1.
(下圖是分解過程，圖自python編程實現歸並排序)
合並的過程如下:
很好，你現在可以和別人說，老子會歸並排序了。但是讓你寫代碼出來，相信你是不會的……
來來來，看我用python寫的歸並排序演算法:
defmerge_sort(array):# 遞歸分解 mid=int((len(array)+1)/2) iflen(array)==1:# 遞歸結束的條件，分解到列表只有一個數據時結束 returnarray list_left=merge_sort(array[:mid]) list_right=merge_sort(array[mid:]) print(">>>list_left:", list_left) print(">>>list_right:", list_right) returnmerge(list_left, list_right)# 進行歸並 defmerge(list_left, list_right):# 進行歸並 final=[] whilelist_leftandlist_right: iflist_left[0] <=list_right[0]:# 如果將"<="改為"<",則歸並排序不穩定 final.append(list_left.pop(0)) else: final.append(list_right.pop(0)) returnfinal+list_left+list_right# 返回排序好的列表 if__name__=="__main__": array=[49,38,65,97,76] print(merge_sort(array))輸出:
輸出：
>>>list_left: [49]
>>>list_right: [38]
>>>list_left: [38, 49]
>>>list_right: [65]
>>>list_left: [97]
>>>list_right: [76]
>>>list_left: [38, 49, 65]
>>>list_right: [76, 97]
[38, 49, 65, 76, 97]
時間度雜度: 平均情況＝最好情況＝最壞情況＝O(nlogn)
空間復雜度:O(n)
穩定性:穩定
對序列{ 6, 5, 3, 1, 8, 7, 2, 4 }進行歸並排序的實例如下:
使用歸並排序為一列數字進行排序的宏觀過程:
以上就是本文的全部內容，希望對大家的學習有所幫助
⑶ VB 編程中的順序查找和折半查找怎麼編的
1.順序查找沒什麼說的，就是
for(int
i=0;i<len;i++)
if(arr[i]==data)
return
i;
return
-1;
2.折半就是設計low,high
int
low=0;
int
high=len-1;
int
mid;
while(low<=high)
{
mid=(low+high)/2;
if(data>arr[mid])
low=mid+1;
else
if(data<arr[mid])
high=mid-1;
else
return
mid;
}
緝弧光舊叱攪癸些含氓return
-1;
⑷ 如何編程實現「折半查找」的過程
將這一句if(f=0)
printf("Not Found");
改為
if(start>end)
printf("Not Found");
你的程序的問題：如果輸入的數據不在數組中，f值也會改變，因為第一次循環的時候if、else if、else必然會執行一個，而其中的每個都會改變f的值。
⑸ C語言編程之拆半查找法
首先數組就得按從大到小或者從小到大先排列好，代碼裡面的數組已經按照從小到大的順序排好了，這叫預排序，沒有預排序就無法進行折半查找。。。。如世
折半查找，你要先確定一個頭和一個尾，就像上面的top與bot，而你要查找的數據肯定會在頭與尾之間那段數組中（前提是數組裡面一定含有你要查找的數據）。。。。
那麼為了加快查找速度，我們可以先拿頭與尾中間的那個數據，與所要查找的數據（下面用c來表示該數據）進行比較，中間那個數的位置就在mid=(top+bot)/2。。。。
舉這樣的例子吧，從1到100的數中查找c。。。。
如果中間數50等於c，那就可以直接得出它在數組中的位置了，就是mid，代碼if(c==a[mid])的作用就是這樣。。。。
要說明一下，為什麼它顯示的代碼printf("the position is %d\n",mid+1)中，mid要加1，如一個數在數組中的位置為0，那它就是在第一位，這個應該好理解吧。。。。
接著，如果中間數50小於c，那就說明了c的位置應該在中間到末尾那個位置，也就是51到100那個位置，代碼if(c>a[mid])就是這樣的意思，比較後，就把top=mid+1，即a[top]=51，再從51至100裡面尋找c。。。。
如果中間數50大於c，那就表示c的位置應該在頭到中間那個位置，就是說在1到49那個位置，對吧，代碼中最後那個else起這樣的作用，把bot=mid-1，也就是說a[bot]=49，通過循環，再從1至49裡面尋找c。。。。
其實折半查找的思想很簡單，就是比較中間數與查找數，判斷出查找數是在前半段，還是在後半段，還是就等於中間數，如果在前半段，拿把前半段分離出來，再用其中間數與查找數比較，就這樣不斷循環，最終找到結果為止。。。。
數組若很差衡大，如有1000個數，一個個進行比較的話，最差也得比較1000次，這樣很耗費時間與資源，折半查找法就能比較好地減少了循環的次數。。。。
當然虛橡做，前提是數組要預排序，如果是亂序的話，是不能用折半的。。。。
若還有什麼不清楚，可以密我。。。。