分治法二分搜索演算法c語言

❶ 用c語言編二分查找

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
void xuanzhe(int a[], int n)
{
int i, j, min, t;

for (i=0; i<n-1; i++) /*要選擇的次數：0~n-2共n-1次*/
{
min = i; /*假設當前下標為i的數最小，比較後再調整*/
for (j=i+1; j<n; j++)/*循環找出最小的數的下標是哪個*/
{
if (a[j] < a[min])
{
min = j; /*如果後面的數比前面的小，則記下它的下標*/
}
}

if (min != i) /*如果min在循環中改變了，就需要交換數據*/
{
t = a[i];
a[i] = a[min];
a[min] = t;
}
}
}
int main(){
int i,n,x;
int mid,left=0,right=999;
int find1=0,find2=0;
double y;
int a[1000];
for(i=0;i<1000;++i){
a[i]=rand();
}
xuanzhe(a,1000);
scanf("%d",&x);
printf("順序查找:\n");
for(i=0;i<1000;++i){
while(x==a[i]){
printf("找到X=%d,a[%d]\n",x,i);
find1=1;
break;
}
}
if(find1==0){
printf("沒有你要找的數\n");
}

printf("%fs\n",clock()/CLOCKS_PER_SEC);
y=clock();
printf("二分查找:\n");
while(!find2&&left<right)
{
mid=(left+right)/2;
if(x==a[mid])
find2=1;
else if(x<a[mid])
right=mid-1;
else left=mid+1;
}
if(find2==1)
printf("找到x=%d ,a[%d]\n",x,mid);
else
printf("沒有你要找的數\n");
printf("%fs\n",(clock()-y)/CLOCKS_PER_SEC);
}

❷ 一道C語言的題目 二分查找演算法和插入元素

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
// 定義數組初始長度
#define LEN 10
// 生成隨機數組
void get_array(int * a, int n)
{
srand(time(NULL));
for (int i = 0; i < n; i++)
a[i] = rand() % 90 + 10;
}

// 列印數組
void print_array(int * a, int n)
{
for (int i = 0; i < n; i++)
{
printf("%d ", a[i]);
}
printf(" ");
}

// 冒泡排序
void bubble_sort(int * a, int n)
{
int i, j, temp;
for (j = 0; j < n - 1; j++)
{
for (i = 0; i < n - 1 - j; i++)
{
if(a[i] < a[i + 1])
{
temp = a[i];
a[i] = a[i + 1];
a[i + 1] = temp;
}
}
}
}

// 二分查找，a是數組,n是數組長度,element是要查找的元素
// 找到返回元素所在的下標,否則返回-1
int binary_search(int * a, int n, int element)
{
int low = 0, high = n - 1, middle = 0;
middle = (low + high) / 2;
int pos = -1;
while (low <= high)
{
if (element == a[middle])
return pos = middle;
else if (element > a[middle])
{
high = middle - 1;
middle = (low + high) / 2;
}
else
{
low = middle + 1;
middle = (low + high) / 2;
}
}
return pos;
}

// 向長度為n的數組a中插入元素element
void insert(int * a , int n, int element)
{
a = (int *)realloc(a, n + 1);

for (int i = 0; i <= n; i++)
{
if (a[i] > element)
continue;
for (int j = n; j > i; j--)
{
a[j] = a[j-1];
}
a[i] = element;
break;
}
}

// 測試
int main()
{
int *array = (int *)malloc(LEN);
if (NULL == array)
{
printf("內存分配失敗 ");
return -1;
}
int element = 0;
get_array(array, LEN);
printf("生成的隨機數組: ");
print_array(array, LEN);
bubble_sort(array, LEN);
printf("排序後的數組: ");
print_array(array, LEN);

printf("請輸入查找的元素: ");
scanf("%d", &element);
int pos = binary_search(array, LEN, element);
if (-1 == pos)
{
printf("未找到元素[%d] ", element);
insert(array, LEN, element);
printf("插入新元素[%d]後的數組: ", element);
print_array(array, LEN + 1);
}
else
printf("元素[%d]所在的位置為[%d] ", element, pos);

free(array);
return 0;
}

❸ c語言 最快的查找方式

1、最快的查找方式是：二分法查找。
2、查找的線性表分：無序線性表、有序線性表、分塊有序線性表。
3、對無序線性表只能採用順序查找，順序查找的平均比較次數為（n+1)/2
4、對有序線性表可以採用二分查找，二分查找的比較次數為log2n
5、對分塊有序線性表可以採用分塊法查找。

C語言是一種計算機程序設計語言，它既具有高級語言的特點，又具有匯編語言的特點。它由美國貝爾研究所的D.M.Ritchie於1972年推出，1978年後，C語言已先後被移植到大、中、小及微型機上，它可以作為工作系統設計語言，編寫系統應用程序，也可以作為應用程序設計語言，編寫不依賴計算機硬體的應用程序。它的應用范圍廣泛，具備很強的數據處理能力，不僅僅是在軟體開發上，而且各類科研都需要用到C語言，適於編寫系統軟體，三維，二維圖形和動畫，具體應用比如單片機以及嵌入式系統開發。

❹ C語言 二分查找演算法 用遞歸實現 我改動了一下

本人直接打出來的，並未在平台上編譯運行過，所以可能會有語法錯位，還請自行調試更改
#include<stdio.h>

int RecorBinarySearch(int a[], int, int, int);
int main(void)
{
int i=0, n, m, key;
int a[10000], c[10000];

scanf("%d", &n);
scanf("%d", &m);

printf("提示：輸入%d個整數且必須按升序排列。\n", n);
for(i=0; i<n; i++){
scanf("%d", &a[i]);
}
printf("提示：輸入%d個預查找的數。\n", m);
for(i=0; i<m; i++){
scanf("%d", &key);
c[i] = RecorBinarySearch(a, key, 0, n-1);
}
printf("提示：輸出預查找的數在數組中的位置。（-1代表未找到）\n");
for(i=0; i<m; i++) {
printf("%d ", c[i]);
}
return 0;
}

int RecorBinarySearch(int a[], int key, int low, int high)
{
int nRet;
if(low > high)
nRet = -1;
else {
int mid = (high + low) / 2;
if(key == a[mid])
nRet = mid;
else if(key > a[mid])
nRet = RecorBinarySearch(a, key, mid+1, high);
else if(key < a[mid])
nRet = RecorBinarySearch(a, key, low, mid-1);
}
return nRet;
}

❺ 二分搜索演算法

#include <stdio.h>

#include <stdlib.h>

int a[100]={1,2,3,5,12,12,12,15,29,55};//數組中的數（由小到大）

int k;

void found(int &x,int &y,int k) //在x與y之間，要找k

{

if(x>y)return;

int m=x+(y-x)/2;

if(a[m]==k)x=y=m;

else if(a[m]>k)found(x,y=m-1,k);//找左邊

else found(x=m+1,y,k);//找右邊

}

int main()

{ int i=0,j=9;

scanf("%d",&k);//輸入要找的數字k

found(i,j,k);//從數組a[0]到a[9]中找k

if(i==j)printf("a[%d]==%d ",i,k);

else printf("a[%d]==%d a[%d]==%d, k==%d ",j,a[j],i,a[i],k);

return 0;

}

❻ c語言編程二分查找

好久不寫了

寫一個程序，建立N元整型數組，然後輸入查找的整數x，查找x是否包含在數組中，查找用函數實現，若查找成功，返回x在數組中的第一次出現的下標，查找失敗，返回－1

源程序：
#include"stdio.h"
#define N 10
int locate(int a[N],int x)
{int h,r,m;
h=0;r=N-1;m=(h+r)/2;
while(h<=r&&x!=a[m])
if(x<a[m]) {r=m-1;m=(h+r)/2;}
else {h=m+1;m=(h+r)/2;}
if(h>r) return -1; /*查找失敗，返回－1*/
return m; /*查找成功，返回有效下標m */
}
void upinsert(int a[],int i) /*插入排序 （升序）*/
{int x,j;
x=a[i];j=i-1;
while(j>=0&&a[j]>x) {a[j+1]=a[j];j--;}
a[j+1]=x;
}
void main()
{int a[N],x,k,n;
printf("input %d integers:\n",N);
for(k=0;k<N;k++) {scanf("%d",a+k);upinsert(a,k);}
printf("input x=") ;scanf("%d",&x);
n=locate(a,x);
for(k=0;k<N;k++) printf("%4d",a[k]);
printf("\n fist position=%d\n",n);
}

沒有錯誤，我試過了

❼ C語言問題求解，二分查找

二分查找也稱折半查找，它是一種效率較高的查找方法。但是，折半查找要求線性表必須採用順序存儲結構，而且表中元素按關鍵字有序排列。

#include <stdio.h>

int cnt;

int binfind(int a[],int l,int r,int x)

{ cnt++;

int m=(l+r)/2;

if(l>m)return -1;

if(x==a[m])return m;

if(x>a[m])return binfind(a,m+1,r,x);

return binfind(a,l,m-1,x);

}

int main()

{ int n,i,x,a[100];

scanf("%d",&n);

for(i=0; i<n; i++)

scanf("%d",&a[i]);

scanf("%d",&x);

i=binfind(a,0,n-1,x);

printf("%d %d ",i,cnt);

return 0;

}

❽ C語言遞歸函數如何實現二分搜索演算法

折半查找法也稱為二分查找法，它充分利用了元素間的次序關系，採用分治策略，可在最壞的情況下用O(log n)完成搜索任務。它的基本思想是，已知一個有n個元素的有序序列, 將n個元素分成個數大致相同的兩半，取a[n/2]與欲查找的x作比較，如果x=a[n/2]則找到x，演算法終止。如果x<a[n/2]，則我們只要在數組a的左半部繼續搜索x（這里假設數組元素呈升序排列）。如果x>a[n/2]，則我們只要在數組a的右半部繼續搜索x, 直到找到x或者是沒有找到!

如果是常規的方法的話那麼我們可以通過循環的方式, 按照上面說的演算法, 找到則退出循環, 否則繼續循環直到左下標位置小於或者等於右下標的位置.

按兄弟你的意思是要用遞歸方法進行搜索, 那麼大概還是上面的演算法, 只是把循環的方式改成遞歸方式: 如果沒找到,則確定新的搜索范圍, 即左右下標新位置, 然後把新的參數傳給函數繼續調用函數進行遞歸搜索!!

遞歸方式實現詳細代碼如下:

#include <stdio.h>

#define ARRAY_SIZE 10
#define NOT_FOUND -1

int BinarySearch(int array[], int left, int right, int NumToSearch)
{
int mid = (left + right) / 2;

if (left <= right)
{
if (NumToSearch == array[mid])
{
return mid;
}
else if (NumToSearch < array[mid])
{
right = mid - 1;
return BinarySearch(array, left, right, NumToSearch);
}
else
{
left = mid + 1;
return BinarySearch(array, left, right, NumToSearch);
}
}

return NOT_FOUND;
}

int main()
{
int a[ARRAY_SIZE] = {2, 5, 6, 7, 13, 20, 22, 27, 112, 222};//假設一個已知的有序且是升序數列
int result = 0;//查找的結果
int x = 13;//假設我們要查找的數是13
int left = 0;//序列開始下標
int right = ARRAY_SIZE - 1;//序列結尾下標

result = BinarySearch(a, left, right, x);
if (result == NOT_FOUND)
{
printf("Not Found!\n");
}
else
{
printf("Found %d in array a, it is a[%d]\n", x, result);
}

return 0;

}

希望對兄弟你有幫助!

❾ 怎樣寫二分查找演算法的程序（用C語言實現）

我用一個子函數實現的，主函數你自己寫，對你又好處，需要傳入一個數組和數組長度n以及要查找的數,如果查找成功，返回x在數組中的位置，否則返回-1
int search(int *a,int x)
{ int low=0,high=n-1,mid,flag=-1;
while(low<=high)
{ mid=(low+high)/2;
if(a[mid]==x) return mid;
else if(a[mid]>low) low=mid+1;
else high=mid-1;
}
return flag;
}

❿ 用C語言編寫順序查找和二分查找（折半查找）

#include<stdio.h>
#defineLENGTH20

voidSequenceSearch(int*fp,intLength);
voidSearch(int*fp,intlength);
voidSort(int*fp,intlength);

voidmain()
{
intcount;
intarr[LENGTH];

printf("請輸入你的數據的個數:
");
scanf("%d",&count);
printf("請輸入%d個數據
",count);
for(inti=0;i<count;i++)
{
scanf("%d",&arr[i]);
}

intchoise=0;
do
{
printf("1.使用順序查詢.
2.使用二分查找法查找.
3.退出
");
scanf("%d",&choise);

if(choise==1)
SequenceSearch(arr,count);
elseif(choise==2)
Search(arr,count);
elseif(choise==3)
break;
}while(choise==1||choise==2||choise==3);
}

voidSequenceSearch(int*fp,intLength)
{
intdata;
printf("開始使用順序查詢.
請輸入你想要查找的數據.
");
scanf("%d",&data);

for(inti=0;i<Length;i++)
if(fp[i]==data)
{
printf("經過%d次查找，查找到數據%d.
",i+1,data);
return;
}

printf("經過%d次查找，未能查找到數據%d.
",i,data);
}

voidSearch(int*fp,intlength)
{
intdata;
printf("開始使用順序查詢.
請輸入你想要查找的數據.
");
scanf("%d",&data);
printf("由於二分查找法要求數據是有序的，現在開始為數組排序.
");
Sort(fp,length);
printf("數組現在已經是從小到大排列,下面將開始查找.
");

intbottom,top,middle;

bottom=0;
top=length;

inti=0;
while(bottom<=top)
{
middle=(bottom+top)/2;
i++;
if(fp[middle]<data)
{
bottom=middle+1;
}
elseif(fp[middle]>data)
{
top=middle-1;
}
else
{
printf("經過%d次查找，查找到數據%d.
",i,data);
return;
}
}
printf("經過%d次查找，未能查找到數據%d.
",i,data);
}

voidSort(int*fp,intlength)
{
printf("現在開始為數組排序，排列結果將是從小到大.
");

inttemp;
for(inti=0;i<length;i++)
for(intj=0;j<length-i-1;j++)
if(fp[j]>fp[j+1])
{
temp=fp[j];
fp[j]=fp[j+1];
fp[j+1]=temp;
}

printf("排序完成!
下面輸出排序後的數組:
");
for(intk=0;k<length;k++)
{
printf("%5d",fp[k]);
}
printf("
");

}