`

binary search - c

 
阅读更多

binary search - c (simple)

 

search - basic:

 

/** @author kuchaguangjie@gmail.com */
#include <stdio.h>
/**
 * binary search (simple)
 *
 * @param 
 * 	arr	pointer of array
 * @param 
 * 	len	length of array
 * @param 
 *	x	target to search
 *
 * @return
	index of target in the array,return -1 if not found, 
 */
int bin_search(int *arr,int len,int x) {
	// indexs 
	int start = 0,end = len-1,middle;
	while (end >= start) {
		middle = (start + end) >> 1;
		if (*(arr+middle)==x) {
			return middle;
		} else if(x < *(arr+middle)) {
			end = middle - 1;
		} else {
			start = middle + 1;
		}
	}
	// not found
	return -1;
}

int main() {
	int arr_1[8] = {0,1,3,4,6,7,9,10};
	int i_1 = bin_search(arr_1,8,3);
	int i_2 = bin_search(arr_1,8,9);
	int i_3 = bin_search(arr_1,8,5);
	int i_4 = bin_search(arr_1,8,15);
	int i_5 = bin_search(arr_1,8,-5);
	printf("expect:\n\t2,6,-1,-1,-1\n");
	printf("actural:\n\t%d,%d,%d,%d,%d\n",i_1,i_2,i_3,i_4,i_5);
}
 

 

search - first / last / all

/** @author kuchaguangjie@gmail.com */
#include <stdio.h>
/**
 * binary search, search the first match,
 *
 * @param 
 * 	arr	pointer of array
 * @param 
 * 	len	length of array
 * @param 
 *	x	target to search
 *
 * @return
	index where target first appear in the array,return -1 if not found, 
 */
int bin_search_first(int *arr,int len,int x) {
	// indexs 
	int start = 0,end = len-1,middle;
	while (end > start) { // here must be '>', not '>=', otherwise endless loop might happen,
		middle = (start + end) >> 1;
		if(*(arr+middle) < x) {
			start = middle + 1;
		} else {
			end = middle;
		}
	}
	if(*(arr+start) == x) {
		return start;
	} else {
		// not found
		return -1;
	}
}

int test_search_first() {
	int len = 17;
	int arr_1[17] = {0,1,3,4,6,7,7,7,7,7,7,7,7,7,7,9,10};
	int i_0 = bin_search_first(arr_1,len,7);
	int i_1 = bin_search_first(arr_1,len,3);
	int i_2 = bin_search_first(arr_1,len,9);
	int i_3 = bin_search_first(arr_1,len,5);
	int i_4 = bin_search_first(arr_1,len,15);
	int i_5 = bin_search_first(arr_1,len,-5);
	printf("expect:\n\t5,2,15,-1,-1,-1\n");
	printf("actural:\n\t%d,%d,%d,%d,%d,%d\n",i_0,i_1,i_2,i_3,i_4,i_5);
}

/**
 * binary search, search the last match,
 *
 * @param 
 * 	arr	pointer of array
 * @param 
 * 	len	length of array
 * @param 
 *	x	target to search
 *
 * @return
	index where target last appear in the array,return -1 if not found, 
 */
int bin_search_last(int *arr,int len,int x) {
	// indexs 
	int start = 0,end = len-1,middle;
	while (end > start) { // here must be '>', not '>=', otherwise endless loop might happen,
		middle = (start + end + 1) >> 1; // here must be '(start + end + 1)', not '(start + end)', otherwise endless loop might happen,
		if(*(arr+middle) > x) {
			end = middle - 1;
		} else {
			start = middle;
		}
	}
	if(*(arr+end) == x) {
		return end;
	} else {
		// not found
		return -1;
	}
}

int test_search_last() {
	int len = 17;
	int arr_1[17] = {0,1,3,4,6,7,7,7,7,7,7,7,7,7,7,9,10};
	int i_0 = bin_search_last(arr_1,len,7);
	int i_1 = bin_search_last(arr_1,len,3);
	int i_2 = bin_search_last(arr_1,len,9);
	int i_3 = bin_search_last(arr_1,len,5);
	int i_4 = bin_search_last(arr_1,len,15);
	int i_5 = bin_search_last(arr_1,len,-5);
	printf("expect:\n\t14,2,15,-1,-1,-1\n");
	printf("actural:\n\t%d,%d,%d,%d,%d,%d\n",i_0,i_1,i_2,i_3,i_4,i_5);
}

/**
 * result of search all match,
 * first is the index of first match, -1 means no match
 * last is the index of last match, -1 means no match
 * count is the count of match,
 */
typedef struct {int first, last, count;} all_result;

/**
 * binary search, search all match,
 * steps:
 	* first search a match,
	* if not found, then return, over,
	* if found,
		divide the array into 2 part by the found match, 
		search in left part for the first match,and search in the right part for the last match, 
		then combine them, that's the result,
 *
 * @param 
 * 	arr	pointer of array
 * @param 
 * 	len	length of array
 * @param 
 *	x	target to search
 *
 * @return
 	type all_result
 */
all_result * bin_search_all(int *arr,int len,int x) {
	// indexs 
	int start = 0,end = len-1,middle;
	static all_result result;
	result.first = -1;result.last = -1;result.count = 0; // this is a static variable, init it every time,
	while (end >= start) {
		middle = (start + end) >> 1;
		if (*(arr+middle)==x) { // find a match
			result.first = bin_search_first(arr+start,middle-start+1,x)+start;
			result.last = bin_search_last(arr+middle, end-middle+1,x)+middle;
			result.count = result.last - result.first + 1;
			return &result;
		} else if(x < *(arr+middle)) {
			end = middle - 1;
		} else {
			start = middle + 1;
		}
	}
	return &result;
}

int test_search_all() {
	int len = 17;
	int arr_1[17] = {0,1,3,4,6,7,7,7,7,7,7,7,7,7,7,9,10};

	all_result *r_0 = bin_search_all(arr_1,len,7);
	printf("r_0\texpect: [5, 14]:10,\tactrual: [%d, %d]:%d\n",r_0->first,r_0->last,r_0->count);

	all_result *r_1 = bin_search_all(arr_1,len,3);
	printf("r_1\texpect: [2, 2]:1,\tactrual: [%d, %d]:%d\n",r_1->first,r_1->last,r_1->count);
	
	all_result *r_2 = bin_search_all(arr_1,len,9);
	printf("r_2\texpect: [15, 15]:1,\tactrual: [%d, %d]:%d\n",r_2->first,r_2->last,r_2->count);
	
	all_result *r_3 = bin_search_all(arr_1,len,5);
	printf("r_3\texpect: [-1, -1]:0,\tactrual: [%d, %d]:%d\n",r_3->first,r_3->last,r_3->count);
	
	all_result *r_4 = bin_search_all(arr_1,len,15);
	printf("r_4\texpect: [-1, -1]:0,\tactrual: [%d, %d]:%d\n",r_4->first,r_4->last,r_4->count);
	
	all_result *r_5 = bin_search_all(arr_1,len,-5);
	printf("r_5\texpect: [-1, -1]:0,\tactrual: [%d, %d]:%d\n",r_5->first,r_5->last,r_5->count);
}

int main() {
	test_search_all();
}
 
分享到:
评论

相关推荐

    c语言-leetcode题解之0095-unique-binary-search-trees-ii.zip

    c语言基础 c语言_leetcode题解之0095_unique_binary_search_trees_ii.zip

    c语言-leetcode题解之0099-recover-binary-search-tree.zip

    c语言基础 c语言_leetcode题解之0099_recover_binary_search_tree.zip

    c语言-leetcode题解之0098-validate-binary-search-tree.zip

    c语言基础 c语言_leetcode题解之0098_validate_binary_search_tree.zip

    c语言-leetcode题解之0096-unique-binary-search-trees.zip

    c语言基础 c语言_leetcode题解之0096_unique_binary_search_trees.zip

    2-is-a-C-binary-search-algorithm.zip_visual c

    4. **编写代码**:在新创建的源文件中,你可以编写二分查找的函数,如`int binarySearch(int arr[], int target, int low, int high)`,并实现上述的逻辑。 5. **主函数**:创建一个主函数`int main()`,用于测试二...

    Ordered-binary-search-table.zip_Table

    这个示例定义了一个名为`binarySearch`的函数,它接受一个排序数组、目标值和数组的左右边界作为参数。在主函数`main`中,我们创建了一个有序数组,并调用`binarySearch`函数查找目标值,最后输出结果。 ### 4. ...

    Binary-search.c

    Binary-search.c

    c语言-leetcode题解之0704-binary-search

    c语言入门 c语言_leetcode题解之0704_binary_search

    c语言-leetcode题解之0235-lowest-common-ancestor-of-a-binary-search

    c c语言_leetcode题解之0235_lowest_common_ancestor_of_a_binary_search

    Binary_Search_Data.rar_binary_binary search

    在“BinarySearch”这个C程序中,可能会包含如下关键部分: - 定义函数原型,如`int binarySearch(int arr[], int target, int left, int right)`。 - 主函数调用`binarySearch`并处理返回结果。 - 在`binarySearch`...

    binary tree C语言算法

    在计算机科学中,二叉树(Binary Tree)是一种数据结构,每个节点最多有两个子节点,通常分为左子节点和右子节点。这种数据结构广泛应用于各种算法和问题解决,如搜索、排序、文件系统等。在C语言中实现二叉树,我们...

    Binary Search Tree

    Binary Search Tree 利用C++實現 Binary Search Tree

    binary-search-clang

    这个程序定义了一个`binarySearch`函数,它接受一个已排序的整数数组、目标值、搜索区间的起始和结束索引作为参数。通过不断地调整搜索区间,直到找到目标元素或搜索区间为空。如果找到目标元素,返回其索引;否则,...

    binary search tree.rar_Binary_Search_Tree_tree

    在给定的“binary search tree program using c language”中,我们可以期待找到一个用C语言实现的二叉搜索树程序。C语言是一种底层编程语言,适合编写这样的数据结构实现,因为它允许直接操作内存,使得程序执行更...

    折半查找 减治法-C语言

    1. **定义函数原型**:声明一个函数,例如`int binarySearch(int arr[], int left, int right, int target)`,这个函数接受一个有序数组、起始索引、结束索引和目标值作为参数。 2. **基础条件**:检查左右边界是否...

    哈工大-计算机-考研复试-机试-C语言.zip

    1. **8_2折半查找.cpp**:折半查找(Binary Search)是一种在有序数组中查找特定元素的搜索算法。它通过比较中间元素来逐步缩小搜索范围,具有较高的效率。此题可能要求考生实现折半查找算法并理解其工作原理。 2. ...

    Binary-Tree 代码

    在二叉搜索树(Binary Search Tree, BST)中,有以下关键特性: 1. **特性**:对于任意节点,其左子树中的所有节点的值都小于该节点的值;其右子树中的所有节点的值都大于该节点的值。这种特性使得二叉搜索树在查找...

    binary_search_tree.zip

    二叉排序树(Binary Search Tree,BST),也称为二叉查找树或有序二叉树,是一种自平衡的二叉树数据结构。它具有以下特性: 1. 每个节点包含一个键(key)、一个关联的值、一个指向左子树的指针和一个指向右子树的...

    apkmirror_search-0.0.1-py3-none-any.whl.zip

    文件名的结构遵循PEP 427,包括了项目名、版本、Python解释器兼容性标识(如"py3"表示Python 3)、ABI(Application Binary Interface)标识(如"none"表示与特定ABI无关)以及平台标识(如"any"表示平台无关)。...

    一组改进的二进制搜索算法_binary-search_二分搜索_c语言

    最常用的二分搜索变体由 Hermann Bottenbruch 于 1962 年首次发布,此后没有明显变化。下面我将描述几个具有改进性能的新变体。最值得注意的变体是单向二分搜索,它在小于 100 万个 32 位整数的数组上的执行速度比...

Global site tag (gtag.js) - Google Analytics