用遞歸方法寫出有序數(shù)組的二分查找算法

什么是二分查找？

為慶城等地區(qū)用戶提供了全套網(wǎng)頁設(shè)計(jì)制作服務(wù)，及慶城網(wǎng)站建設(shè)行業(yè)解決方案。主營業(yè)務(wù)為成都網(wǎng)站制作、成都做網(wǎng)站、慶城網(wǎng)站設(shè)計(jì)，以傳統(tǒng)方式定制建設(shè)網(wǎng)站，并提供域名空間備案等一條龍服務(wù)，秉承以專業(yè)、用心的態(tài)度為用戶提供真誠的服務(wù)。我們深信只要達(dá)到每一位用戶的要求，就會(huì)得到認(rèn)可，從而選擇與我們長期合作。這樣，我們也可以走得更遠(yuǎn)！

二分查找也稱折半查找（Binary Search），它是一種效率較高的查找方法。但是，折半查找要求線性表必須采用順序存儲(chǔ)結(jié)構(gòu)，而且表中元素按關(guān)鍵字有序排列。

二分查找優(yōu)缺點(diǎn)

優(yōu)點(diǎn)是比較次數(shù)少，查找速度快，平均性能好；

其缺點(diǎn)是要求待查表為有序表，且插入刪除困難。

因此，折半查找方法適用于不經(jīng)常變動(dòng)而查找頻繁的有序列表。

使用條件：查找序列是順序結(jié)構(gòu)，有序。

過程

首先，假設(shè)表中元素是按升序排列，將表中間位置記錄的關(guān)鍵字與查找關(guān)鍵字比較，如果兩者相等，則查找成功；否則利用中間位置記錄將表分成前、后兩個(gè)子表，如果中間位置記錄的關(guān)鍵字大于查找關(guān)鍵字，則進(jìn)一步查找前一子表，否則進(jìn)一步查找后一子表。重復(fù)以上過程，直到找到滿足條件的記錄，使查找成功，或直到子表不存在為止，此時(shí)查找不成功。

利用循環(huán)的方式實(shí)現(xiàn)二分法查找

public class BinarySearch {

public static void main(String[] args) {

// 生成一個(gè)隨機(jī)數(shù)組 ? ? ? ?int[] array = suiji();

// 對(duì)隨機(jī)數(shù)組排序 ? ? ? ?Arrays.sort(array);

System.out.println("產(chǎn)生的隨機(jī)數(shù)組為： " + Arrays.toString(array));

System.out.println("要進(jìn)行查找的值： ");

Scanner input = new Scanner(System.in);

// 進(jìn)行查找的目標(biāo)值 ? ? ? ?int aim = input.nextInt();

// 使用二分法查找 ? ? ? ?int index = binarySearch(array, aim);

System.out.println("查找的值的索引位置： " + index);

}

/** ? ? * 生成一個(gè)隨機(jī)數(shù)組 ? ? *

* @return 返回值，返回一個(gè)隨機(jī)數(shù)組 ? ? */

private static int[] suiji() {

// random.nextInt(n)+m ?返回m到m+n-1之間的隨機(jī)數(shù) ? ? ? ?int n = new Random().nextInt(6) + 5;

int[] array = new int[n];

// 循環(huán)遍歷為數(shù)組賦值 ? ? ? ?for (int i = 0; i array.length; i++) {

array[i] = new Random().nextInt(100);

}

return array;

}

/** ? ? * 二分法查找 ?---循環(huán)的方式實(shí)現(xiàn) ? ? *

* @param array 要查找的數(shù)組 ? ? * @param aim 要查找的值 ? ? * @return 返回值，成功返回索引，失敗返回-1 ? ? */

private static int binarySearch(int[] array, int aim) {

// 數(shù)組最小索引值 ? ? ? ?int left = 0;

// 數(shù)組最大索引值 ? ? ? ?int right = array.length - 1;

int mid;

while (left = right) {

mid = (left + right) / 2;

// 若查找數(shù)值比中間值小，則以整個(gè)查找范圍的前半部分作為新的查找范圍 ? ? ? ? ? ?if (aim array[mid]) {

right = mid - 1;

// 若查找數(shù)值比中間值大，則以整個(gè)查找范圍的后半部分作為新的查找范圍 ? ? ? ? ? ?} else if (aim array[mid]) {

left = mid + 1;

// 若查找數(shù)據(jù)與中間元素值正好相等，則放回中間元素值的索引 ? ? ?} else {

return mid;

}

}

return -1;

}}

運(yùn)行結(jié)果演示：

由以上運(yùn)行結(jié)果我們得知，如果要查找的數(shù)據(jù)在數(shù)組中存在，則輸出該數(shù)據(jù)在數(shù)組中的索引；如果不存在則輸出 -1 ，也就是打印 -1 則該數(shù)在數(shù)組中不存在，反之則存在。

四、利用遞歸的方式實(shí)現(xiàn)二分法查找

public class BinarySearch2 {

public static void main(String[] args) {

// 生成一個(gè)隨機(jī)數(shù)組 ? ? ? ?int[] array = suiji();

// 對(duì)隨機(jī)數(shù)組排序 ? ? ? ?Arrays.sort(array);

System.out.println("產(chǎn)生的隨機(jī)數(shù)組為： " + Arrays.toString(array));

System.out.println("要進(jìn)行查找的值： ");

Scanner input = new Scanner(System.in);

// 進(jìn)行查找的目標(biāo)值 ? ? ? ?int aim = input.nextInt();

// 使用二分法查找 ? ? ? ?int index = binarySearch(array, aim, 0, array.length - 1);

System.out.println("查找的值的索引位置： " + index);

}

/** ? ? * 生成一個(gè)隨機(jī)數(shù)組 ? ? * ? ? * @return 返回值，返回一個(gè)隨機(jī)數(shù)組 ? ? */

private static int[] suiji() {

// Random.nextInt(n)+m ?返回m到m+n-1之間的隨機(jī)數(shù) ? ? ? ?int n = new Random().nextInt(6) + 5;

int[] array = new int[n];

// 循環(huán)遍歷為數(shù)組賦值 ? ? ? ?for (int i = 0; i array.length; i++) {

array[i] = new Random().nextInt(100);

}

return array;

}

/** ? ? * 二分法查找 ---遞歸的方式 ? ? * ? ? * @param array 要查找的數(shù)組 ? ? * @param aim ? 要查找的值 ? ? * @param left ?左邊最小值 ? ? * @param right 右邊最大值 ? ? * @return 返回值，成功返回索引，失敗返回-1 ? ? */

private static int binarySearch(int[] array, int aim, int left, int right) {

if (aim array[left] || aim array[right]) {

return -1;

}

// 找中間值 ? ? ? ?int mid = (left + right) / 2;

if (array[mid] == aim) {

return mid;

} else if (array[mid] aim) {

//如果中間值大于要找的值則從左邊一半繼續(xù)遞歸 ? ? ? ? ? ?return binarySearch(array, aim, left, mid - 1);

} else {

//如果中間值小于要找的值則從右邊一半繼續(xù)遞歸 ? ? ? ? ? ?return binarySearch(array, aim, mid + 1, array.length-1);

}

}}

運(yùn)行結(jié)果演示：

總結(jié)：

遞歸相較于循環(huán)，代碼比較簡(jiǎn)潔，但是時(shí)間和空間消耗比較大，效率低。在實(shí)際的學(xué)習(xí)與工作中，根據(jù)情況選擇使用。通常我們?nèi)绻褂醚h(huán)實(shí)現(xiàn)代碼只要不是太繁瑣都選擇循環(huán)的方式實(shí)現(xiàn)~

編寫一個(gè)在有序表中二分查找給定關(guān)鍵字記錄的遞歸算法 (C語言)

其實(shí)這個(gè)書本上可以找到的，邏輯也比較容易實(shí)現(xiàn)。我寫一下主要的邏輯吧。

int Serch(int * a, int low, int high. int key)

{

if (low = high)

{

int mid = ( high - low) / 2 + low;

if (key == a[mid]) // 找到了

return mid;

else if (key a[mid]) // 比中間值小，向前找

Serch(a, low, mid - 1, key);

else // 向后找

Serch(a, mid + 1, high, key);

}

return -1; // 沒找到

}

用遞歸的方式實(shí)現(xiàn)二分查找c語言

#include stdio.h

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

int k;//要找的數(shù)字

int found(int x,int y)

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

if(xy)//查找完畢沒有找到答案，返回-1

return -1;

else

{ if(a[m]==k) return m;//找到就返回位置.

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

else return found(m+1,y);//找右邊

}

}

int main()

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

printf("%d\n",found(0,9));//從數(shù)組a[0]到a[9]進(jìn)行查找

return 0;

}

C語言中使用函數(shù)實(shí)現(xiàn):數(shù)據(jù)的輸入,排序,輸出和查找(要求折半查找遞歸實(shí)現(xiàn)) 在線等

#include stdio.h

#define N 5 /*數(shù)組的大小*/

void input(int *a,int n)/*輸入函數(shù)*/

{

int *p=a;

while(pa+n)

scanf("%d",p++);

}

void output(int *a,int n)/*輸出函數(shù)*/

{

int *p=a;

while(pa+n)

printf("%d ",*p++);

printf("\n");

}

void isort(int *s,int n)/*排序函數(shù)*/

{

int i,j;

int *p,temp;

for(i=0;in-1;i++)

{

p=s+i;

for(j=i;jn;j++)

if(*ps[j])

p=s+j;

temp=*p;

*p=s[i];

s[i]=temp;

}

}

int binsh(int *a, int c, int low, int high)/*遞歸法實(shí)現(xiàn)的二分查找法，元素存在于a中則返回元素的第一個(gè)位置，不存在則返回-1*/

{

int mid=(high+low)/2;

if(lowhigh)

return -1;

if(ca[mid])

return binsh(a,c,mid+1,high);

else if(ca[mid])

return binsh(a,c,low,mid-1);

else

return mid;

}

int main()

{

int a[N],n;

input(a,N);/*輸入*/

isort(a,N);/*排序*/

output(a,N);/*輸出*/

scanf("%d",n);/*要查找的元素*/

printf("%d\n",binsh(a,n,0,N-1));/*存在的話打印位置，不存在的話打印-1*/

return 0;

}

有用的話，請(qǐng)樓主及時(shí)采納，謝謝

用C語言寫二分查找的代碼?。?！

推薦答案的 code 有問題，并沒有考慮到若待查數(shù)的下標(biāo)是 0 怎么辦？所以若順序表中不存在待查元素?應(yīng)該 return?-1

加上主函數(shù)的最后兩行調(diào)用兩次查找函數(shù)很多余，代碼顯得不夠簡(jiǎn)練。

建議改成：

#include?stdio.h

#include?stdlib.h

int?Search(int?*a,?int?key)

{

//?在順序表中折半查找?key的數(shù)據(jù)元素。若找到，則函數(shù)值為

int?low?=?0,?mid;?//?該元素的數(shù)組下標(biāo)；否則為0。

int?high?=?14;

while?(low?=?high)

{

mid?=?(low?+?high)?/?2;

if?(key?==?a[mid])

return?mid;?//?找到待查元素

else?if?(key??a[mid])

high?=?mid?-?1;?//?繼續(xù)在前半?yún)^(qū)間進(jìn)行查找

else

low?=?mid?+?1;?//?繼續(xù)在后半?yún)^(qū)間進(jìn)行查找

}

return?-1;?//?順序表中不存在待查元素

}

void?main()

{

int?*a,?key,?i;

int?b[15]?=?{0};

a?=?b;

printf("請(qǐng)自小到大輸入15個(gè)整數(shù)：\n");

for?(i?=?1;?i?=?15;?i++)

{

scanf("%d",?b[i?-?1]);

printf("\n");

}

printf("請(qǐng)輸入你要查找的數(shù)：\n");

scanf("%d",?key);

i?=?Search(a,?key);

if?(-1?==?i)

printf("你要查找的數(shù)不在目標(biāo)數(shù)組中！\n");

else

printf("你要查找的數(shù)的數(shù)組下標(biāo)為?%d?\n",?i);

}

C語言二分查找法

#include stdio.h

int binfind(int val[] , int num , int value)

{

int start = 0;

int end = num - 1;

int mid = (start + end)/2;

while(val[mid] != value start end)

{

if (val[mid] value)

{

end = mid - 1;

}

else if (val[mid] value)

{

start = mid + 1;

}

mid = ( start + end )/2;

}

if (val[mid] == value)

return mid;

else

return -1;

}

int main()

{

int nums[] = {1 , 3 , 4 ,7 ,8 , 12 ,45 ,67 ,97 ,123 ,456 ,675 ,1111 , 4534 , 4563};

int result = binfind(nums , sizeof(nums) / sizeof(nums[0]) , 45);

if (result 0)

{

printf("查無此數(shù)");

}

}

分享名稱：二分查找遞歸函數(shù)c語言 c語言用遞歸實(shí)現(xiàn)二分法查找
標(biāo)題來源：http://chinadenli.net/article44/dodijhe.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供做網(wǎng)站、網(wǎng)站營銷、品牌網(wǎng)站設(shè)計(jì)、標(biāo)簽優(yōu)化、網(wǎng)站策劃、全網(wǎng)營銷推廣

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)