折半查找（递归）——ANSI C实现

偏执的太偏执、 2022-05-16 22:05 172阅读 0赞

typedef int ElementType;

/*
     * 递归的二分搜索
     *
     * 输入参数1：待搜索序列
     * 输入参数2：最低下标
     * 输入参数3：最高下标
     * 输入参数4：关键码
     *
     * 输出类型：匹配元素的下标，若没有找到，则返回-1
     *
     * */
    int RecursionBSearch(ElementType *arr, int low, int high, ElementType key) {
    	int mid = (high + low) / 2;
    
    	if (low <= high) {
    		// 若关键码小于中间元素值，则进入左半区搜索
    		if (key < arr[mid])
    			return RecursionBSearch(arr, low, mid - 1, key);
    
    		// 若关键码大于中间元素值，则进入右半区搜索
    		else if (key > arr[mid])
    			return RecursionBSearch(arr, mid + 1, high, key);
    
    		// 若关键码等于中间元素值，则返回下标
    		else if (key == arr[mid])
    			return mid;
    	}
    
    	return -1;
    }

int Search(ElementType *arr, int size, ElementType key) {
    	// 检查参数
    	if (arr == NULL || size <= 0)
    		return -1;
    
    	return RecursionBSearch(arr, 0, size - 1, key);
    }

int main() {
    
    	int size = 30;
    	int max = 300;
    	int *array = GetRandomArray(size, max);
    	printf("Original ");
    	PrintArray(array, size);
    	Sort(array, size);
    	printf("Sorted   ");
    	PrintArray(array, size);
    
    	srand(clock());
    	int key = rand() % max;
    	int pos = Search(array, size, key);
    	if (pos != -1)
    		printf("Key element %d has been found in position %d of this array...", key, pos);
    	else
    		printf("Cannot find key element %d in this sorted array...", key);
    
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，172人围观）

还没有评论，来说两句吧...

相关阅读

相关 C语言实现：折半查找算法（递归、分治法）

C语言实现：折半查找算法（递归）（分治法）文章目录 C语言实现：折半查找算法（递归）（分治法） 1. 问题 2. 解决方案

一时失言乱红尘/ 2024年03月31日 16:15/ 0 赞/ 59 阅读

相关递归折半查找，C语言

include <stdio.h> /折半查找/ int binary_Search(int arry, int key, int left,

﹏ヽ暗。殇╰゛Y/ 2023年06月10日 06:22/ 0 赞/ 3 阅读

相关 #数据结构折半查找的递归和非递归算法

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

深藏阁楼爱情的钟/ 2023年02月18日 03:25/ 0 赞/ 10 阅读

相关 PHP折半查找递归函数,递归的折半查找算法

代码部分： \include \define MAXL 100 typedef int KeyType; typedef char InfoType\[10\]; t

系统管理员/ 2023年01月17日 15:49/ 0 赞/ 197 阅读

相关折半查找的递归和非递归实现

折半查找的递归和非递归实现 <pre name="code" class="cpp">include<iostream> using namespace st

墨蓝/ 2022年08月09日 15:53/ 0 赞/ 213 阅读

相关递归法实现折半查找

include <stdio.h> int BinSearch(int a,int low,int high,int key) {

末蓝、/ 2022年07月13日 09:54/ 0 赞/ 190 阅读

相关 Java实现折半查找(二分查找)的递归和非递归算法

转　：　[http://wintys.blog.51cto.com/425414/94051][http_wintys.blog.51cto.com_425414_94051]

偏执的太偏执、/ 2022年07月12日 09:16/ 0 赞/ 211 阅读

相关递归应用：折半查找法

折半查找法介绍在计算机科学中，折半搜索（英语：half-interval search），也称二分搜索（英语：binary search）、对数搜索（英语：logari

左手的ㄟ右手/ 2022年06月01日 11:13/ 0 赞/ 198 阅读

相关折半查找（迭代）——ANSI C实现

typedef int ElementType; int Search(ElementType arr, int size, ElementType

╰半夏微凉°/ 2022年05月16日 22:06/ 0 赞/ 149 阅读

相关折半查找（递归）——ANSI C实现

typedef int ElementType; / 递归的二分搜索输入参数1：待搜索序列

偏执的太偏执、/ 2022年05月16日 22:05/ 0 赞/ 173 阅读