您好,登錄后才能下訂單哦!
二分查找也稱折半查找(Binary Search),它是一種效率較高的查找方法。但是,折半查找要求線性表必須采用順序存儲結(jié)構(gòu),而且表中元素按關(guān)鍵字有序排列。
通常在查找數(shù)組的時候,會發(fā)現(xiàn)一個一個查找很浪費(fèi)資源,因此通過二分查找法實(shí)現(xiàn) 。
算法要求:
1.必須采用順序存儲結(jié)構(gòu)。
2.必須按關(guān)鍵字大小有序排列。
首先,假設(shè)表中元素是按升序排列,將表中間位置記錄的關(guān)鍵字與查找關(guān)鍵字比較,如果兩者相等,則查找成功;否則利用中間位置記錄將表分成前、后兩個子表,如果中間位置記錄的關(guān)鍵字大于查找關(guān)鍵字,則進(jìn)一步查找前一子表,否則進(jìn)一步查找后一子表。重復(fù)以上過程,直到找到滿足條件的記錄,使查找成功,或直到子表不存在為止,此時查找不成功。
(上面是思維導(dǎo)圖)
#include<stdio.h>
#include <windows.h>
//while、do while 、goto、for、遞歸
void digui(int shang,int xia,int zhong,int num)
{
zhong = (shang + xia) / 2;
if (shang <= xia)
{
if (num == zhong)
{
printf("遞歸:find.%d\n", zhong);
return;
}
else if (num < zhong)
{
xia = zhong - 1;
printf("shang.%d,zhong.%d,xia.%d \n", shang, zhong, xia);
}
else
{
shang = zhong + 1;
printf("shang.%d,zhong.%d,xia.%d \n", shang, zhong, xia);
}
}
return;
}
int main()
{
int a[1024];
for (int i = 0; i<1024; i++) {
a[i] = i;
//printf("%d\n",a[i]);
}
int shang = 0;
int xia = 1023;
int zhong = (shang + xia) / 2;
int num = 102;
while (shang <= xia)//一、while
{
zhong = (shang + xia) / 2;
if (num == zhong)
{
printf("while:find.%d\n", zhong);
break;
}
else if (num < zhong)
{
xia = zhong - 1;
printf("shang.%d,zhong.%d,xia.%d \n", shang, zhong, xia);
}
else
{
shang = zhong + 1;
printf("shang.%d,zhong.%d,xia.%d \n", shang, zhong, xia);
}
}
printf("==================\n");
printf("==================\n");
printf("==================\n");
shang = 0;
xia = 1023;
zhong = (shang + xia) / 2;
num = 102;
do {//二、do while
zhong = (shang + xia) / 2;
if (num == zhong)
{
printf("do while:find.%d\n", zhong);
break;
}
else if (num < zhong)
{
xia = zhong - 1;
printf("shang.%d,zhong.%d,xia.%d \n", shang, zhong, xia);
}
else
{
shang = zhong + 1;
printf("shang.%d,zhong.%d,xia.%d \n", shang, zhong, xia);
}
} while (xia>=shang);
printf("==================\n");
printf("==================\n");
printf("==================\n");
shang = 0;
xia = 1023;
zhong = (shang + xia) / 2;
num = 988;
AAA://三、goto
zhong = (xia + shang) / 2;
if (num == zhong)
{
printf("goto:find.%d\n", zhong);
goto BBB;
}
else if (num > zhong)
{
shang = zhong + 1;
printf("shang.%d,zhong.%d,xia.%d \n", shang, zhong, xia);
}
else
{
xia = zhong - 1;
printf("shang.%d,zhong.%d,xia.%d \n", shang, zhong, xia);
}
if (shang<=xia)
{
goto AAA;
}
BBB:
printf("==================\n");
printf("==================\n");
printf("==================\n");
shang = 0;
xia = 1023;
zhong = (shang + xia) / 2;
num = 288;
for (int i; shang <= xia ;zhong = (shang + xia) / 2)
{
if (num == zhong)
{
printf("for:find.%d\n", zhong);
break;
}
else if (num < zhong)
{
xia = zhong - 1;
printf("shang.%d,zhong.%d,xia.%d \n", shang, zhong, xia);
}
else
{
shang = zhong + 1;
printf("shang.%d,zhong.%d,xia.%d \n", shang, zhong, xia);
}
}
printf("==================\n");
printf("==================\n");
printf("==================\n");
shang = 0;
xia = 1023;
zhong = (shang + xia) / 2;
num = 288;
digui(shang,xia,zhong,num); //遞歸
getchar();
getchar();
Sleep(5000);
return 0;
}
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。