- 浏览: 442788 次
- 性别:
- 来自: 深圳
文章分类
- 全部博客 (158)
- J2SE (15)
- c/c++ (17)
- linux & ubuntu (20)
- js (18)
- algorithm (21)
- android (1)
- software (3)
- svn (1)
- db (6)
- other (19)
- css (5)
- go (1)
- html 5 (3)
- computer science (1)
- php (3)
- 创业 (8)
- EJB & jboss (1)
- TDD (1)
- jsp & servlet (2)
- http, tcp & ip (2)
- hibernate (1)
- json (1)
- 乐 (2)
- ps (2)
- netbeans (1)
- extjs (2)
- eclipse (4)
- 项目管理 (1)
- varnish (2)
- study abroad (1)
- python (1)
- erlang (1)
- math (1)
- shell (1)
- assembly (4)
- lucene (1)
- web (1)
- http (1)
- tcp & ip (1)
最新评论
-
yiguxianyun:
...
css li 不换行 -
stdayong:
...
netbeans 中使用 maven -
程序猿_星:
为啥会中文乱码啊
servlet 以 gzip 格式返回数据 -
huanhuan519:
感谢分享~
gdb 调试工具 -
heyl1234:
写过些js,对css还不熟。谢谢~
css li 不换行
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 - linkedlist
2012-05-10 14:52 1080c - linkedlist store ordere ... -
c - word counter (binary-tree)
2012-05-09 14:17 1724c - word counter (binary-tree) ... -
c - pointer is also pass by value
2012-05-09 14:13 969c - pointer is also pass by ... -
find palindromic-prime in pi
2012-04-26 18:32 1846find palindromic-prime in pi ... -
c #define
2012-04-08 13:29 2103c #define macro substitu ... -
c static
2012-04-04 21:59 1235c static static external ... -
c extern
2012-04-04 21:53 1152c extern extern, used to de ... -
int to string by specified base
2012-04-03 22:15 1076int to string by specified base ... -
random select
2011-08-28 01:00 1204random select problem: ... -
sparse data structure - matrix
2011-08-18 20:03 1079sparse data structure sp ... -
max sub_sequence - c
2011-08-10 01:02 1072max sub_sequence - c /* ... -
bit_array - simple use
2011-05-28 23:47 1006bit array,use less memory to de ... -
linux c udp
2011-04-01 18:02 2090linux 下可用 c 进行 udp 通信,使用 server ... -
linux c tcp
2011-04-01 18:00 3062linux 下可用 c 进行 tcp 通信,使用 server ... -
gdb 调试工具
2011-02-21 17:20 3313gdb 调试工具 gdb 概 ... -
linkedlist - java 简单实现
2011-02-11 21:29 1592linked list 链表, - ... -
queue (用 java 简单实现)
2011-02-03 01:45 4047queue ------ 结构 线性存 ... -
Medians and Order Statistics (次序统计)
2011-01-03 14:36 2827Medians and Order Statistics - ... -
counting sort
2011-01-02 20:36 1562counting sort ------ counting ... -
quick sort
2011-01-01 20:26 1188quicksort ------ quicksort ove ...
相关推荐
c语言基础 c语言_leetcode题解之0095_unique_binary_search_trees_ii.zip
c语言基础 c语言_leetcode题解之0099_recover_binary_search_tree.zip
c语言基础 c语言_leetcode题解之0098_validate_binary_search_tree.zip
c语言基础 c语言_leetcode题解之0096_unique_binary_search_trees.zip
4. **编写代码**:在新创建的源文件中,你可以编写二分查找的函数,如`int binarySearch(int arr[], int target, int low, int high)`,并实现上述的逻辑。 5. **主函数**:创建一个主函数`int main()`,用于测试二...
这个示例定义了一个名为`binarySearch`的函数,它接受一个排序数组、目标值和数组的左右边界作为参数。在主函数`main`中,我们创建了一个有序数组,并调用`binarySearch`函数查找目标值,最后输出结果。 ### 4. ...
Binary-search.c
c语言入门 c语言_leetcode题解之0704_binary_search
c c语言_leetcode题解之0235_lowest_common_ancestor_of_a_binary_search
在“BinarySearch”这个C程序中,可能会包含如下关键部分: - 定义函数原型,如`int binarySearch(int arr[], int target, int left, int right)`。 - 主函数调用`binarySearch`并处理返回结果。 - 在`binarySearch`...
在计算机科学中,二叉树(Binary Tree)是一种数据结构,每个节点最多有两个子节点,通常分为左子节点和右子节点。这种数据结构广泛应用于各种算法和问题解决,如搜索、排序、文件系统等。在C语言中实现二叉树,我们...
Binary Search Tree 利用C++實現 Binary Search Tree
这个程序定义了一个`binarySearch`函数,它接受一个已排序的整数数组、目标值、搜索区间的起始和结束索引作为参数。通过不断地调整搜索区间,直到找到目标元素或搜索区间为空。如果找到目标元素,返回其索引;否则,...
在给定的“binary search tree program using c language”中,我们可以期待找到一个用C语言实现的二叉搜索树程序。C语言是一种底层编程语言,适合编写这样的数据结构实现,因为它允许直接操作内存,使得程序执行更...
1. **定义函数原型**:声明一个函数,例如`int binarySearch(int arr[], int left, int right, int target)`,这个函数接受一个有序数组、起始索引、结束索引和目标值作为参数。 2. **基础条件**:检查左右边界是否...
1. **8_2折半查找.cpp**:折半查找(Binary Search)是一种在有序数组中查找特定元素的搜索算法。它通过比较中间元素来逐步缩小搜索范围,具有较高的效率。此题可能要求考生实现折半查找算法并理解其工作原理。 2. ...
在二叉搜索树(Binary Search Tree, BST)中,有以下关键特性: 1. **特性**:对于任意节点,其左子树中的所有节点的值都小于该节点的值;其右子树中的所有节点的值都大于该节点的值。这种特性使得二叉搜索树在查找...
二叉排序树(Binary Search Tree,BST),也称为二叉查找树或有序二叉树,是一种自平衡的二叉树数据结构。它具有以下特性: 1. 每个节点包含一个键(key)、一个关联的值、一个指向左子树的指针和一个指向右子树的...
文件名的结构遵循PEP 427,包括了项目名、版本、Python解释器兼容性标识(如"py3"表示Python 3)、ABI(Application Binary Interface)标识(如"none"表示与特定ABI无关)以及平台标识(如"any"表示平台无关)。...
最常用的二分搜索变体由 Hermann Bottenbruch 于 1962 年首次发布,此后没有明显变化。下面我将描述几个具有改进性能的新变体。最值得注意的变体是单向二分搜索,它在小于 100 万个 32 位整数的数组上的执行速度比...