快捷導(dǎo)航

C語言編程中實(shí)現(xiàn)二分查找的簡單入門實(shí)例

更新時(shí)間：2015年12月02日 11:51:22 作者：dazhong159

這篇文章主要介紹了C語言編程中實(shí)現(xiàn)二分查找的簡單入門實(shí)例,需要的朋友可以參考下

架設(shè)有一個(gè)數(shù)組 v 已經(jīng)按升序排列了，數(shù)組 v 有 n=20 個(gè)元素。數(shù)組中有個(gè)元素 x，如何知道 x 位于該數(shù)組的第幾位呢？
解決這個(gè)問題的一個(gè)普遍方法就是二分查找法。下面是程序：

#include <stdio.h>
int binsearch(int x, int v[], int n);
main()
{
  int i, result, n;
 int wait;
  
  int x = 17; // 需要查找的數(shù)值
 int v[19]; // 定義一個(gè)數(shù)組
 // 給數(shù)組賦值
 for(i = 0; i < 20; ++i)
   v[i] = i;
 /**
 for(i = 0; i < 20; ++i)
 printf("%d \n", v[i]);
 */
 n = 20;
 result = binsearch(x, v, n);
 printf("%d", result);
 scanf("%d", &wait);
}
int binsearch(int x, int v[], int n)
{
 int low, high, mid;
 low = 0;
 high = n - 1;
 while (low <= high)
 {
 mid = (low + high) / 2;
 if(x < v[mid])
  high = mid - 1;
 else if (x > v[mid])
  low = mid + 1;
 else
  return mid;
 // 看看循環(huán)執(zhí)行了多少次
 printf("mid = %d, low = %d, high = %d \n", mid, low, high);
 }
 return -1;
}

1、二分查找法

二分查找法有一個(gè)很重要的前提條件：即待查找的序列必須是已經(jīng)排好序的。

假設(shè)元素序列是按升序排列，將序列中間位置記錄的關(guān)鍵字與查找關(guān)鍵字比較，如果兩者相等，則查找成功；否則利用中間位置記錄將序列分成前、后兩個(gè)子序列，如果中間位置記錄的關(guān)鍵字大于查找關(guān)鍵字，則進(jìn)一步查找前一子序列，否則進(jìn)一步查找后一子序列。重復(fù)以上過程，直到找到滿足條件的記錄，查找成功，返回元素在序列中的索引，或直到子序列不存在為止，此時(shí)查找失敗，返回-1。

int find2(int *array,int n,int val) 
{ 
  if (n<=0) 
  { 
    return -1; 
  } 
 
  int begin=0,end=n-1,mid; 
  while(begin<=end)       
  { 
    mid=(begin+end)/2; 
    if (array[mid]==val) 
      return mid; 
    else if(array[mid]>val) 
      end=mid-1; 
    else 
      begin=mid+1; 
  } 
 
  return -1; 
}

2、使用二分查找樹查找

首先創(chuàng)建一顆二分查找樹，我們知道二分查找樹的特點(diǎn)是左子樹的值都比根節(jié)點(diǎn)小，右子樹的值都比根節(jié)點(diǎn)大，且二分查找樹的中序遍歷所得到的元素是排好序的。

//二叉查找樹數(shù)據(jù)結(jié)構(gòu) 
typedef struct Btree 
{ 
  int data; 
  Btree *left; 
  Btree *right; 
}*PBTree; 
 
//創(chuàng)建二叉查找樹，返回樹的根節(jié)點(diǎn) 
PBTree CreateBTree(int *array,int n) 
{ 
  PBTree root=new Btree; 
  root->data=array[0]; 
  root->left=NULL; 
  root->right=NULL; 
 
  PBTree current,back,pNew; 
  for (int i=1;i<n;i++) 
  { 
    pNew=new Btree; 
    pNew->data=array[i]; 
    pNew->left=pNew->right=NULL; 
    current=root; 
    while(current!=NULL)  //找到合適的插入位置 
    { 
      back=current; 
      if(current->data>array[i]) 
        current=current->left; 
      else 
        current=current->right; 
    } 
    if(back->data>array[i]) 
      back->left=pNew; 
    else 
      back->right=pNew; 
  } 
 
  return root; 
} 
 
//利用二叉查找樹進(jìn)行遞歸查找 
bool find3(PBTree root,int val) 
{ 
  if (root==NULL) 
    return false; 
  if (root->data==val) 
    return true; 
  else if(root->data>val) 
    return find3(root->left,val); 
  else 
    return find3(root->right,val); 
}

3、總結(jié)

二分查找有非常嚴(yán)格的限制條件（序列必須是有序的）；

而使用二分查找樹，則會自動(dòng)創(chuàng)建出"有序樹"（中序遍歷得到的序列是有序的）；

不考慮二叉查找樹的建立時(shí)間，二者的效率一樣，均為O（logn）。

您可能感興趣的文章: