(二分法）C语言程序

1、打开Python开发工具IDLE,新建‘search.py’。

2、F5运行程序，list1被正确排序，写这个的目的是说明二分法查找必须前提是一个有序的列表，如果一开始无序首先要排序，当数据量大的时候，快速排序是一个很好的选择，再进行二分法查找。

3、用递归的思想，递归就一定有结束条件。

4、if len(li)==1:   #li长度等于1，只比较这个列表元素与要查找到值return li[0]==item。

5、if len(li)==0: #li长度等于0，全部查找结束还是没有这个值  return False。

6、为程序添加main方法。

7、F5运行程序，正确打印出二分法查找结果，False True。

#include <stdio.h>

int a[10]={21,56,43,12,3,99,56,23,2,12}

main()

{

int i,j,k,low,high,mid,t

for(i=k=1i<sizeof a/sizeof a[0]i++)//起始认为第一个元素是有序的,high=low=k-1=0,所以k=1,

{

low=0

high=k-1

while(low<=high)////折半查找时，low与high相遇，则找到插入位置

{

mid=(low+high)/2

if(a[mid]>=a[i])high=mid-1///////元素比mid小，因此在low到mid-1范围内搜索位置

else low=mid+1

}

if(high<i|| a[low]!=a[i]) ///////////

{

t=a[i]

for(j=k-1j>=lowj--) //////插入位置是low，所以low到high=k-1范围内的元素都要向后移动

a[j+1]=a[j]

a[low]=t//////////////low被赋值为已经被覆盖掉的a[i]

k++

}

}

for(j=0j<kj++)

printf("%4d",a[j])

printf("\n")

}

自己修改一下，把注释去了，能运行，刚刚运行过了。

#include<stdlib.h>

void sort(int a[],int n){ /*排序函数，要使用二分法查找就必须对数组进行排序*/

int i,k

for(i=0i<ni++){

int min=i

for(k=i+1k<nk++)

if(a[min]>a[k])min=k

if(i!=min){

a[min]+=a[i]/*这里是运用加减法交换两个数*/

a[i]=a[min]-a[i]

a[min]-=a[i]

}

}

}int find(int a[],int n,int key){/*二分法查找；参数：数组名，数组长度，查找关键字*/

int min=0,max=n-1/*二分法查找头尾变量*/

while(min<max){/*如果最头的变量值大于最尾变量的值，则查找不到，查找失败*/

int cen = (min+max)/2

if(a[cen]==key) return cen/*如果查到，则返回关键字在排序数组的下标*/

if(cen==min || cen==max)break/*如果中间变量等于头尾任一个变量，同样查找失败*/if(a[cen]>key) max=cen

else min=cen }

return -1

}

void main(){/*主程序只是为了证明两个函数的可行性，可以自己编写*/

int a[]={14,10,25,36,87,95,10,12,13,8},i

sort(a,10)

i=find(a,10,11)

if(i!=-1)

printf("be found")

else

printf("no found")

getch()

}

---