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

偏执的太偏执、 2022-05-16 22:05 139阅读 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 条评论，139人围观）

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

相关阅读

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

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

r囧r小猫/ 2024年03月31日 16:15/ 0 赞/ 29 阅读

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

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

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

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

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

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

相关 java的递归折半查询,java递归

package day01; /\\ \ 递归: 在功能(方法)中直接、间接调用了功能(方法)本身 \ \ 老和尚讲故事()\{ \ 1) 从前有座山 \ 2) 山

旧城等待，/ 2022年11月18日 02:25/ 0 赞/ 150 阅读

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

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

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

相关递归法实现折半查找

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

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

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

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

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

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

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

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

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

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

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

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

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

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