CWYAlpha

Just another WordPress.com site

Thought this was cool: 数据结构重读 – 顺序和二分查找、最/次优查找树、索引顺序表查找

leave a comment »


概念明天补上。。。

顺序查找,用了哨兵减少检查数组长度的次数,据说这样可以让顺序查找的性能提升一倍

优点:无序任何假设条件(如数组有序等)。

缺点:效率低。

#include <stdio.h>

int ssearch(int* arr, int n, int key)
{
    int i = 0;
    arr[n] = key;
    for(i=0;arr[i]!=key;i++);
    if(i==n)
    {
        return -1;
    }else {
        return i;
    }
}

int main()
{
    int arr[9] = {5, 4, 7, 43, -42, 56,  -1};
    int key = -42;
    int n = sizeof(arr) / sizeof(int) - 1; // Reserve last one for SHao Bing
    printf("Search for 13: %d", ssearch(arr, n, key));
    return 0;
}

二分查找:据说98%的程序员写不对,我这个是不是也有Bug呢?

#include <stdio.h>

int bsearch(int* arr, int n, int key)
{
	int low = 0, high = n-1, mid = 0;
	while(low<=high)
	{
		mid = (low+high)/2;
		if(arr[mid]==key)
		{
			return mid;
		} else if(arr[mid]<key)
		{
			low = mid + 1;
		} else
		{
			high = mid - 1;
		}
	}
	return -1;
}

int main()
{
	int arr[8] = {1, 3, 5, 7, 9, 12, 18, 123};
	int key = 12;
	printf("Search for 13: %d", bsearch(arr, sizeof(arr)/sizeof(int), key));
	return 0;
}

 

 

 
from 四号程序员四号程序员: http://www.coder4.com/archives/3519

Written by cwyalpha

七月 1, 2012 在 3:38 下午

发表在 Uncategorized

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s

%d 博主赞过: