广州wap网站制作/网站内容优化方法

开篇

算法是神奇的。

IT技术日新月异，各种语言、工具、平台快速更迭着。

而算法、数据结构，几乎是不会过时的。

之前学习了算法与数据结构，但是总感觉没有用武之地，对算法的认识大多仅限于”程序设计大赛”。因为不常用，所以渐渐生疏。

前阵子在学习lighttpd的源码，发现里面的算法、数据结构几乎贯穿了整个项目，数组、字符串、链表、树等数据结构以及二分查找等算法的灵活应用，使得整个项目的逻辑更加清晰，而效率也提升了许多。

我这才见识到算法与数据结构在工程应用中的重要性。

我们日常的学习中，大多学的是最标准的算法版本，然而实际问题却千变万化，实际用到的算法也常常是标准版本的变形。所以，光靠“背算法”是很难有成效的，我们需要理解一个算法背后的思想，才能以不变应万变。

在接下来，我将重新把一些常用的经典算法捋一遍，力求理解算法的内涵。

说到算法，我想大家对二分算法并不陌生，但是能快速写出正确的代码的人却不多。接下来，我们将以二分算法及其变形为例，开始走进算法的重修之路。

二分查找

也许我说，麻烦你快速写一个二分查找的算法，为简单起见，写个递归版本的吧!

然后刷刷刷下面的代码就出来了：

int binarySearch(int arr[], int left, int right, int x)
{if (left <= right){int mid = left + (right-left)/2;if (arr[mid] == x) return mid;else if (arr[mid] > x) return binarySearch(arr, left, mid-1, x);else return binarySearch(arr, mid+1, right, x);}return -1;
}

以上代码似乎已经挺完美了。

可是，要是arr==NULL呢？要是arr是降序排序的呢？？

这就涉及两个问题：

1.代码的健壮性

我们只需修改下if条件：

    if (NULL != arr && left <= right)

就可以让我们的程序更加健壮。

2.明确需求，对症下药

对于这一点，我觉得《编程珠玑》就讲的很精彩，里面从一个排序算法讲起，从一开始的“我要对一些文件排序”一步步挖掘需求，从盲目的归并算法到针对特定范围内的整数的位图排序。

所以在面试中，或者在实际应用中，如果你能够多问一句：“数组是升序还是降序？”我想就能少犯错误。

下面我们来写一写非递归版本(只考虑数组升序)，并指出一些常见的问题：

int binarySearch(int arr[], int left, int right, int x)
{/* Notice1: 保证输入的有效性 */if (NULL == arr || right < left) return -1;int mid;/* Notice2: 等号保证了只剩下一个元素时的正确性 */while (left <= right){mid = left + (right-left)/2;if (arr[mid] == x) return mid;/* Notice3: mid-1而不是mid，否则剩下两个数时可能陷入死循环 */else if (arr[mid] > x) right = mid-1; else  left = mid+1;}return -1;
}

最后别忘了针对各种输入情况进行测试。

**在这里备注一个小技巧：

你可能注意到，我在if语句中进行相等测试的语句是：

if (NULL == arr)

可能更多的人习惯于：

if (arr == NULL)

而我那样写的理由很简单，如果粗心的你一不小心把 == 写成了 = ，那么该语句将变成一个赋值语句，而通常情况下编译器是检测不到这个错误的，因为该语句在语法上是正确的。而对于我的写法，如果 == 写成 = ，由于左边是一个右值，所以该语句在语法上是错误的，编译器将帮我们指出这个错误。

因此，这个小细节体现的是良好的编程习惯。

变形1

在循环有序数组中查找指定元素，也就是说在类似这样的{12,16,18,20,41,100,1,4,6,9}数组中查找指定的元素。

我们使用二分法，当我们取出mid之后，数组将被分成两个部分，每部分有两种可能： 纯有序数组 or 循环有序数组。

如果（arr[mid] >= arr[left]），说明左侧是一个纯有序数组，于是当x<=arr[mid]&&x>=arr[left]时，待测元素肯定会在mid的左侧，其他情形则会在mid的右侧。

如果（arr[mid] < arr[left]），说明右侧是一个纯有序数组，于是当x<=arr[left]&&x>=arr[mid]时，待测元素肯定会在mid的右侧，其他情形则会在mid的左侧。

int search(int arr[], int left, int right, int x)
{if (NULL == arr || right < left) return -1;int mid;while (left <= right){mid = left + (right-left)/2;if (arr[mid] == x) return mid;if (arr[mid] >= arr[left]){if (x <= arr[mid] && x >= arr[left])right = mid-1;else left = mid+1;}else{if (x <= arr[left] && x >= arr[mid])left = mid+1;else right = mid-1;}}return -1;
}

需要注意的是，我们的代码仍然有缺陷。

考虑一下一些特殊情况：

1.纯有序数组是旋转数组的特例，不过显然我们的代码可以处理这种情况。

2.如果数组中的数字是可重复的呢？
比如{1，0，1，1，1}，那么我们的程序在查找0时将失败！因为在我们的程序中，将认为{1，0，1}是一个纯有序数组。
（对于{1，1，1，0，1}，我们的程序能够正确处理）。

为解决这个问题，我们需要对arr[mid] == arr[left] 的情况进行处理。（我的思路：对left到mid部分进行顺序查找，如果该部分的值均相同，说明左侧是一个纯有序数组，否则为循环有序数组。再根据结果进入下一步，具体实现留给读者去思考。）

变形2

假如集合中的元素有重复，要找到x首次出现的位置。

只需要对 arr[mid] == x 的情况进行特殊处理，检查前一个元素是否是重复元素。

int binarySearch(int arr[], int left, int right, int x)
{if (NULL == arr || right < left) return -1;int mid;while (left <= right){mid = left + (right-left)/2;if (arr[mid] == x){if (0 == mid) return mid;if (mid >= 1 && arr[mid-1] != x) return mid;else right = mid-1;}else if (arr[mid] > x) right = mid-1; else  left = mid+1;}return -1;
}

变形3

在一个有序的数组里，数据里面元素可能有重复的，查找指定x所在的索引范围。

例如：int arr[] = {1,2,2,2,2,3,3,3,3,3,6,6,7,9,11,12}; 查找3的话，应该返回[5,9]。

思路1：用二分法随意找一个x的索引，之后往两边找重复的x；

以上算法在x比较多的情况下效率不高。

思路2：两次二分法，第一次找x首次出现的位置（变形2）left，第二次找比x大的数的最小索引right，于是答案为[left，right-1]。

第二次二分的代码（找第一个比x大的数且其索引最小）：

int binarySearch(int arr[], int left, int right, int x)
{if (NULL == arr || right < left) return -1;if (x < arr[left]) return left;int mid;while (left <= right){mid = left + (right-left)/2;if (arr[mid] > x){if (mid > left && arr[mid-1] > x) right = mid-1;return mid;}else  left = mid+1;}return -1;
}

好了~就先讲到这里，每天进步一点点，Come on！
(●’◡’●)

本人水平有限，如文章内容有错漏之处，敬请各位读者指出，谢谢！