程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> C說話編程中完成二分查找的簡略入門實例

C說話編程中完成二分查找的簡略入門實例

編輯:關於C++

C說話編程中完成二分查找的簡略入門實例。本站提示廣大學習愛好者:(C說話編程中完成二分查找的簡略入門實例)文章只能為提供參考,不一定能成為您想要的結果。以下是C說話編程中完成二分查找的簡略入門實例正文


架設有一個數組 v 曾經按升序分列了,數組 v 有 n=20 個元素。數組中有個元素 x,若何曉得 x 位於該數組的第幾位呢?
處理這個成績的一個廣泛辦法就是二分查找法。上面是法式:

#include <stdio.h>
int binsearch(int x, int v[], int n);
main()
{
  int i, result, n;
 int wait;
  
  int x = 17; // 須要查找的數值
 int v[19]; // 界說一個數組
 // 給數組賦值
 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;
 // 看看輪回履行了若干次
 printf("mid = %d, low = %d, high = %d \n", mid, low, high);
 }
 return -1;
}

1、二分查找法

    二分查找法有一個很主要的條件前提:即待查找的序列必需是曾經排好序的。

    假定元素序列是按升序分列,將序列中央地位記載的症結字與查找症結字比擬,假如二者相等,則查找勝利;不然應用中央地位記載將序列分紅前、後兩個子序列,假如中央地位記載的症結字年夜於查找症結字,則進一步查找前一子序列,不然進一步查找後一子序列。反復以上進程,直到找到知足前提的記載,查找勝利,前往元素在序列中的索引,或直到子序列不存在為止,此時查找掉敗,前往-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、應用二分查找樹查找

    起首創立一顆二分查找樹,我們曉得二分查找樹的特色是左子樹的值都比根節點小,右子樹的值都比根節點年夜,且二分查找樹的中序遍歷所獲得的元素是排好序的。

//二叉查找樹數據構造 
typedef struct Btree 
{ 
  int data; 
  Btree *left; 
  Btree *right; 
}*PBTree; 
 
//創立二叉查找樹,前往樹的根節點 
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; 
} 
 
//應用二叉查找樹停止遞歸查找 
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、總結

    二分查找有異常嚴厲的限制前提(序列必需是有序的);

    而應用二分查找樹,則會主動創立出"有序樹"(中序遍歷獲得的序列是有序的);

    不斟酌二叉查找樹的樹立時光,兩者的效力一樣,均為O(logn)。

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved