本文作者:心月

順序查找與二分查找算法介紹

心月IT博客 2019-02-26
摘要:順序查找算法 順序查找是非常簡單常用的查找算法,基本思路:從第一個元素m開始逐個與需要查找的元素x進行比較,當比較到元素值相同(即m=x)時返回元素m的下標,如果比較到最后都沒有找到,則返回-1。該算法的時間復雜度為O(n),如果數據量很大時查找效率會很低。

順序查找算法

    順序查找是非常簡單常用的查找算法,基本思路:從第一個元素m開始逐個與需要查找的元素x進行比較,當比較到元素值相同(即m=x)時返回元素m的下標,如果比較到最后都沒有找到,則返回-1。該算法的時間復雜度為O(n),如果數據量很大時查找效率會很低。

 1 #include<stdio.h>
 2 
 3 /* 順序查找算法
 4    a為數據數組,len為數組a的長度,x為查找的元素 
 5    如果查找成功返回元素x在數組a中的下標,找不到則返回-1 
 6  */ 
 7 int search(int a[],int len, int x)
 8 {
 9     int i;
10     for (i=0; i<len; i++)
11     {
12         if(x==a[i])   
13             return i; // 返回元素的下標 
14     }
15     return -1; // 沒有找到 
16 }
17 
18 int main()
19 {
20     int a[10]={1,3,5,2,0,9,8,4,7,6};
21     int x=2;   // 需要查找的元素
22     int i = search(a, 10, x);
23     if(i!=-1)
24         printf("元素%d在第%d個位置n",x,i+1);
25     else
26         printf("沒有找到元素:%dn",x);
27     return 0;
28 }

 

二分查找算法

    二分查找(又稱為折半查找)是在有序序列中查找比較多的查找算法,基本思路:設有一個從小到大的序列,取中間的元素m進行比較,如果等于需要查找的元素x則返回元素m的下標,若x大于m則再從右邊的區間查找,若x小于m則再從左邊的區間查找,這樣每次減少一半的查找范圍。時間復雜度為O(lgn),查找速度相對順序查找要快很多,但是查找的數據序列必須是有序序列(即數據是從小到大或從大到小排序的)。

 1 #include<stdio.h>
 2 
 3 /* 二分查找算法 
 4    a為數據數組,len為數組a的長度,x為查找的元素 
 5    如果查找成功返回元素x在數組a中的下標,找不到則返回-1 
 6  */ 
 7 int binarySearch(int a[],int len, int x)
 8 {
 9     int mid;          // 中間下標
10     int low=0;        // 區間的左端下標
11     int high=len-1;   // 區間的右端下標
12     
13     while(low <= high)
14     {
15         mid = low + (high-low)/2;  // 計算中間下標, 若使用(low+high)/2可能會有整數溢出:當low和high的值較大時(接近整型數所能表示的范圍),low+high的值就會溢出
16         if(x==a[mid])
17             return mid;    // 若找到返回元素的下標 
18         else if(x>a[mid])
19             low=mid+1;     // 在右半邊區間搜索 
20         else
21             high=mid-1;    // 在左半邊區間搜索 
22     }
23     return -1;   // 沒有找到 
24 }
25 
26 int main()
27 {
28     int a[10]={0,1,2,3,4,5,6,7,8,9}; // 必須是有序序列 
29     int x=7;   // 需要查找的元素
30     int i = binarySearch(a, 10, x);
31     if(i!=-1)
32         printf("元素%d在第%d個位置n",x,i+1);
33     else
34         printf("沒有找到元素:%dn",x);
35     return 0;
36 }

 

文章版權及轉載聲明:

作者:心月 本文地址:http://www.eojird.tw/algorithm/141.html發布于 2019-07-01
文章轉載或復制請以超鏈接形式并注明出處心月IT博客

分享到:
贊(

發表評論

快捷輸入:

    評論列表 (有 0 條評論,人圍觀)參與討論