Home >Backend Development >C#.Net Tutorial >How to implement dichotomy in C language to find array elements

How to implement dichotomy in C language to find array elements

coldplay.xixi
coldplay.xixiOriginal
2021-03-17 14:59:325713browse

C language dichotomy method to implement finding array elements: 1. Recursive algorithm, the code is [if(a[mid] == key) return mid]; 2. Non-recursive algorithm, the code is [while( left < right && a[mid] != key )].

How to implement dichotomy in C language to find array elements

The operating environment of this tutorial: windows7 system, c99 version, DELL G3 computer.

C language dichotomy method to implement finding array elements:

Recursive algorithm

#include<stdio.h>
//二分法实现数组查找
 
//
int recurbinary(int *a, int key, int low, int high)
{
    int mid;
    if(low > high)
        return -1;
    mid = (low + high)/2;
    if(a[mid] == key) return mid;
    else if(a[mid] > key)
         return recurbinary(a,key,low,mid -1);
    else
         return recurbinary(a,key,mid + 1,high);
 
}

Non-recursive algorithm

int binary( int *a, int key, int n )
{
    int left = 0, right = n - 1, mid = 0;
    mid = ( left + right ) / 2;
    while( left < right && a[mid] != key )
    {
        if( a[mid] < key ) {
            left = mid + 1;
        } else if( a[mid] > key ) {
            right = mid - 1;
        }
        mid = ( left + right ) / 2;
    }
    if( a[mid] == key )
        return mid;
    return -1;
}
 
int main(void)
{
int a[10] = {2,4,6,8,10,12,14,16,18,20},t,k,f;
scanf("%d",&t);
k = recurbinary(a,t,2,20);
f = binary(a,t,10);  //非递归算法
if(k == -1){
printf("不存在此数\n");
}else{
printf("%-5d是数组第%d个元素\n%-5d数组的第%d个元素",k,k+1,f,f+1);
}
 
return 0;
}

[Related learning recommendations: C language tutorial video]

The above is the detailed content of How to implement dichotomy in C language to find array elements. For more information, please follow other related articles on the PHP Chinese website!

Statement:
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn