1、5种方式实现二分查找，案例结构：
halfFind.h
#ifndef
_HALFFIND_
#define
_HALFFIND_
/************************************************************************/
/*
初始化长度为L的数组 */
/************************************************************************/
extern
void
initArray(int
*arr,
int
n);
/************************************************************************/
/*
打印数组 */
/************************************************************************/
extern
void
printArr(int
*arr,
int
n);
/************************************************************************/
/*
打印次数 */
/************************************************************************/
extern
void
printTimes(int
pos);
/************************************************************************/
/*
通过While循环的方式实现二分查找 */
/************************************************************************/
extern
int
halfFindByWhile(int
*arr,
int
n,
int
num);
/************************************************************************/
/*
二分查找查询某个数值,通过do-while
*/
/************************************************************************/
extern
int
halfFindByDoWhile(int
*arr,
int
n,
int
num);
/************************************************************************/
/*
二分查找，通过goto语句实现
*/
/************************************************************************/
extern
int
halfFindByGoto(int
*arr,
int
n,
int
num);
/************************************************************************/
/*
通过For循环的方式实现二分查找
*/
/************************************************************************/
extern
int
halfFindByFor(int
*arr,
int
n,
int
num);
/************************************************************************/
/*
通过递归的方式进行查找 */
/************************************************************************/
extern
int
halfFindByRecursion(int
*arr,int
n,int
num);
#endif
halfFuncs.c
#include
<stdio.h>
#include
<stdlib.h>
#include
<time.h>
#include
"halfFind.h"
/************************************************************************/
/*
初始化数组的值 */
/************************************************************************/
//voidinitArray(int *arr,int n)
//{
//
//时间数据类型
//
time_t ts;
//
unsigned int num = time(&ts);
//
//初始化随机数种子
//
srand(num);
//
for (int i = 0; i < n; i++) {
//
arr[i] = rand() % n;
//
}
//}
/************************************************************************/
/*
初始化数组的值 */
/************************************************************************/
void
initArray(int
*arr,
int
n)
{
for (int
i = 0;
i <
n;
i++) {
arr[i]
= i;
}
}
/************************************************************************/
/*
打印数组
*/
/************************************************************************/
void
printArr(int
*arr,
int
n)
{
for (int
i = 0;
i <
n;
i++)
{
printf("%d
",arr[i]);
}
}
/************************************************************************/
/*
打印搜索次数 */
/************************************************************************/
void
printTimes(int
pos) {
printf("\nposition
= %d\n",pos);
}
/************************************************************************/
/*
二分查找查询某个数值,通过While表达式
*/
/************************************************************************/
int
halfFindByWhile(int
*arr,
int
n,
int
num)
{
//参数分别表示开始查询位置，结束查询位置，中间位置
int
start_pos = 0,
end_pos =
n - 1,
middle_pos = 0;
while (start_pos
<= end_pos)
{
middle_pos = (start_pos
+ end_pos) / 2;
//如果中间值恰好是要找的值
if (num
== arr[middle_pos])
{
return
middle_pos;
}
else
if (num
> arr[middle_pos])
{
start_pos =
middle_pos + 1;
}
else
{
end_pos =
middle_pos - 1;
}
}
if (start_pos
> end_pos)
{
printf("\n没有找到\n");
return -1;
}
}
/************************************************************************/
/*
二分查找查询某个数值,通过do-while
*/
/************************************************************************/
int
halfFindByDoWhile(int
*arr,
int
n,
int
num)
{
//参数分别表示开始查询位置，结束查询位置，中间位置
int
start_pos = 0,
end_pos =
n - 1,
middle_pos = 0;
do
{
middle_pos = (start_pos
+ end_pos) / 2;
//如果中间值恰好是要找的值
if (num
== arr[middle_pos])
{
return
middle_pos;
}
else
if (num
> arr[middle_pos])
{
start_pos =
middle_pos + 1;
}
else
{
end_pos =
middle_pos - 1;
}
} while (start_pos
<= end_pos);
if (start_pos
> end_pos)
{
printf("\n没有找到\n");
return -1;
}
}
/************************************************************************/
/*
通过goto语句查找 */
/************************************************************************/
int
halfFindByGoto(int
*arr,
int
n,
int
num)
{
//参数分别表示开始查询位置，结束查询位置，中间位置
int
start_pos = 0,
end_pos =
n - 1,
middle_pos = 0;
flag:middle_pos
= (start_pos +
end_pos) / 2;
//如果中间值恰好是要找的值
if (num
== arr[middle_pos])
{
return
middle_pos;
}
else
if (num
> arr[middle_pos])
{
start_pos =
middle_pos + 1;
}
else
{
end_pos =
middle_pos - 1;
}
if (start_pos
<= end_pos)
{
goto
flag;
}
else
{
printf("\n对不起，没有找到!\n");
return -1;
}
}
/************************************************************************/
/*
通过for循环的方式进行查找
*/
/************************************************************************/
int
halfFindByFor(int
*arr,
int
n,
int
num)
{
//参数分别表示开始查询位置，结束查询位置，中间位置
int
start_pos = 0,
end_pos =
n - 1,
middle_pos = 0;
for (;
start_pos <=
end_pos;)
{
middle_pos = (start_pos
+ end_pos) / 2;
//如果中间值恰好是要找的值
if (num
== arr[middle_pos])
{
return
middle_pos;
}
else
if (num
> arr[middle_pos])
{
start_pos =
middle_pos + 1;
}
else
{
end_pos =
middle_pos - 1;
}
}
if (start_pos
> end_pos)
{
printf("\n对不起，没有找到!\n");
return -1;
}
}
/************************************************************************/
/*
通过递归的方式二分查找 */
/************************************************************************/
int
recursion(int
*arr,
int
n,
int
num,
int
start_pos,int
end_pos,int
middle_pos)
{
if(start_pos
<= end_pos)
{
middle_pos = (start_pos
+ end_pos) / 2;
//如果中间值恰好是要找的值
if (num
== arr[middle_pos])
{
return
middle_pos;
}
else
if (num
> arr[middle_pos])
{
start_pos =
middle_pos + 1;
}
else
{
end_pos =
middle_pos - 1;
}
}
else
{
printf("\n对不起，没有找到!\n");
return -1;
}
recursion(arr,
n,
num,
start_pos,
end_pos,
middle_pos);
}
/************************************************************************/
/*
通过递归的方式进行二分查找
*/
/************************************************************************/
int
halfFindByRecursion(int
*arr,
int
n,
int
num)
{
//参数分别表示开始查询位置，结束查询位置，中间位置
int
start_pos = 0,
end_pos =
n - 1,
middle_pos = 0;
//接收递归返回来的值
return
recursion(arr,
n,
num,
start_pos,
end_pos,
middle_pos);
}
halfFind.c
#include
<stdio.h>
#include
<stdlib.h>
#include
"halfFind.h"
#define
N 45
int
main(int
argc,char
*argv[]){
int
arr[N];
//times表示查找了多少次
//start_pos表示开始查找位置
//end_pos最后位置
//num标识要查找的值
int
pos;
initArray(arr,N);
//打印数组
printArr(arr,
N);
//查找
//1、通过while的方式进行查找
//pos = halfFindByWhile(arr, N, 60);
//2、通过do-while的方式进行查找
//pos = halfFindByDoWhile(arr, N, 60);
//3、通过for循环的方式进行二分查找
//pos = halfFindByGoto(arr,N,30);
//4、通过for循环的方式进行二分查找
//pos = halfFindByFor(arr,N,30);
//5、通过递归的方式实现二分查找
pos =
halfFindByRecursion(arr,N,60);
printTimes(pos);
system("pause");
return 0;
}
2、结合结构体实现栈存储结构，代码如下：
#include
<stdio.h>
#include
<stdlib.h>
#define
N
50
struct
mystack
{
int
top;//栈顶
int
data[N];//存放数据
};
struct
mystack
selfstack = { -1, { 0 } };//栈的初始化
//函数声明
int
isempty();
//1为空
0非空
void
setempty();
//栈设置为空
int
push(int
num);
//压入数据，成功1，失败返回0
int
pop();
//弹出数据
/************************************************************************/
/*
判断栈是否为空 */
/************************************************************************/
int
isempty()
{
if (selfstack.top
== -1)
{
//表示是空的
return 1;
}
else
{
//表示不是空的
return 0;
}
}
/************************************************************************/
/*
将栈设置成为空 */
/************************************************************************/
void
setempty()
{
selfstack.top
= -1;
}
/************************************************************************/
/*
压入数据，成功返回1，失败返回0
*/
/************************************************************************/
int
push(int
num)
{
//一定要记住：要判断栈是否溢出
if (selfstack.top
== N - 1)
{
//压栈失败
return 0;
}
else
{
selfstack.top
+= 1; //小标移动一下
selfstack.data[selfstack.top]
= num;//压入数据
return 1;
}
}
/************************************************************************/
/*
弹出数据 */
/************************************************************************/
int
pop()
{
//判断栈是否为空
if (selfstack.top
== -1)
{
return -1;//栈为空
}
else
{
selfstack.top
-= 1;
return
selfstack.data[selfstack.top
+ 1];//弹出的数据
}
}
int
main(int
argc,
char *argv[])
{
int
a[10] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
int
i = 0;
for (i
= 0; i < 10;
i++)
{
//填充数据
push(a[i]);
}
while (!isempty())
{
printf("%d\n",
pop());//输出数据
}
system("pause");
return 0;
}