- 浏览: 436267 次
- 性别:
- 来自: 深圳
文章分类
- 全部博客 (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 1027c - linkedlist store ordere ... -
c - word counter (binary-tree)
2012-05-09 14:17 1670c - word counter (binary-tree) ... -
c - pointer is also pass by value
2012-05-09 14:13 927c - pointer is also pass by ... -
find palindromic-prime in pi
2012-04-26 18:32 1797find palindromic-prime in pi ... -
c #define
2012-04-08 13:29 2054c #define macro substitu ... -
c static
2012-04-04 21:59 1188c static static external ... -
c extern
2012-04-04 21:53 1111c extern extern, used to de ... -
int to string by specified base
2012-04-03 22:15 1034int to string by specified base ... -
random select
2011-08-28 01:00 1173random select problem: ... -
sparse data structure - matrix
2011-08-18 20:03 1031sparse data structure sp ... -
max sub_sequence - c
2011-08-10 01:02 1038max sub_sequence - c /* ... -
bit_array - simple use
2011-05-28 23:47 971bit array,use less memory to de ... -
linux c udp
2011-04-01 18:02 2036linux 下可用 c 进行 udp 通信,使用 server ... -
linux c tcp
2011-04-01 18:00 3028linux 下可用 c 进行 tcp 通信,使用 server ... -
gdb 调试工具
2011-02-21 17:20 3235gdb 调试工具 gdb 概 ... -
linkedlist - java 简单实现
2011-02-11 21:29 1555linked list 链表, - ... -
queue (用 java 简单实现)
2011-02-03 01:45 4007queue ------ 结构 线性存 ... -
Medians and Order Statistics (次序统计)
2011-01-03 14:36 2776Medians and Order Statistics - ... -
counting sort
2011-01-02 20:36 1525counting sort ------ counting ... -
quick sort
2011-01-01 20:26 1152quicksort ------ quicksort ove ...
相关推荐
Binary-search.c
二分查找2是C经典数据结构算法,希望对大家有点用
用c/c++写的有序表的折半查找,有兴趣的朋友可以看一下
Binary Search Tree 利用C++實現 Binary Search Tree
binary search tree program using c language
二进制搜索 分而治之 大o(log n) 欧米茄(1)
最常用的二分搜索变体由 Hermann Bottenbruch 于 1962 年首次发布,此后没有明显变化。下面我将描述几个具有改进性能的新变体。最值得注意的变体是单向二分搜索,它在小于 100 万个 32 位整数的数组上的执行速度比...
一般的BST中的所有值都大于或等于比较值。 这意味着,所有爬网功能都可以通过进行$$ <> $$比较而向前导航,而不必... 插入c。 删除d。 level_order e。 顺序,前置和后置f。 高度g。 深度h。 均衡? 一世。 重新平衡
binary search tree in c
Binary search tree code written in c language
binary search tree in c
用C寫的二分搜尋,原本是用在資料收集機器上的 可以用二分搜尋法來快速搜尋純文字檔的內容,速度很快
该代码是实现单总线器件的二叉树搜索功能的rom程序。
二叉排序树的完整C++实现,注释丰富,代码结构清晰,即下即用,欢迎交流!
- C Recursive - Python Iterative 0102 Binary Tree Level Order Traversal - Python3 iterative 0103 Binary Tree Zigzag Level Order Traversal - Python3 iterative BFS w Deques 0104 Maximum depth of ...
C中的二进制搜索树 该项目在C中实现了一个二进制搜索树,并通过从作为参数传递给程序的文本文件中读取数据来模拟其使用。 然后,它以3种方式遍历树-Inorder,Preorder和Postorder-将读取的信息写入文本文件中,该...
一个简单的二叉搜索树,注意插入的root节点的选择策略。
假设有一个人要我们猜0-99之间的一个数,那么最好的方法就是从0-99的中间数49开始猜。 如果要猜的数小于49,就猜24(0-48的中间数);如果要猜的数大于49,就猜74(50-99的中间数)。 重复这个过程来缩小猜测的范围...
C语言版二分搜索 实现从文件读取数据,并对文件中的数据进行排序,然后二分搜索
* [Binary Search Tree](https://github.com/kamyu104/LeetCode#binary-search-tree) * [Breadth-First Search](https://github.com/kamyu104/LeetCode#breadth-first-search) * [Depth-First Search]...