一个含有多个元素的数组，有多种排序方式。它可以升序排列，可以降序排列，也可以像我们以前章节说过的，以波浪形方式排序，现在我们要看到的一种是绝对值排序。对于数组A,绝对值排序满足以下条件：|A[i]| < |A[j]|，只要i < j。例如下面的数组就是绝对值排序：
A:-49, 75, 103, -147, 164,-197,-238,314,348,-422
给定一个整数k，请你从数组中找出两个元素下标i,j，使得A[i] A[j] == k。如果不存在这样的元素配对，你返回(-1,-1)。
对于这个题目，我们曾经讨论过当数组元素全是整数时的情况，要找到满足条件的配对(i,j)，我们让i从0开始，然后计算m = k - A[i]，接着在(i 1, n)这部分元素中，使用折半查找，看看有没有元素正好等于m，如果在(i 1,n)中存在下标j，满足A[j] == m 那么我们就可以直接返回配对(i,j)，这种做法在数组元素全是正数，全是负数，以及是绝对值排序时都成立，只是在绝对值排序的数组中，进行二分查找时，需要比对的是元素的绝对值。使用这种查找办法，算法的时间复杂度是O(n*lg(n))。
上面算法形式很紧凑，无论数组全是正数，负数，还是绝对值排序时，都有效。但我们还可以找到效率更高的算法，假设数组中的元素全是同一符号，也就是全是正数，或全是负数时，要找到A[i] A[j] == k，我们可以这么做：
1，让i = 0, j = n-1, 如果A[i] A[j] == k 那么算法结束。
2，如果A[i] A[j] < k, 那么令 i = i 1;
3，如果A[i] A[j] > k, 那么令 j = j -1;
上面步骤一直运行到i == j，或是A[i] A[j] == k为止。这种做法的时间复杂度是O(n)。其算法效率比前面提到的方法要好，但问题在于，这种做法不能运用于绝对值排序的数组。为了能够应对绝对值排序的数组，我们需要对算法做一些改进。
对于满足A[i] A[j] == k的元素，它必定满足下面三种情况之一：
1，A[i]和A[j]都是正数。
2，A[i]和A[j]都是负数。
3，A[i]和A[j]是一正一负。
对于前两种情况我们可以直接使用刚才使用的方法，对于第三种情况，我们需要做一个调整，对于第三种情况，我们让i指向最后一个整数，让j指向最后一个负数，如果A[i] A[j] == k，那么算法结束，如果A[i] A[j] > k, 那么让i指向下一个正数，如果A[i] A[j] < k，那么让j指向下一个负数。
因此在查找满足条件的元素配对时，我们先看看前两种情况是否能查找到满足条件的元素，如果不行，那么我们再依据第三种情况去查找，无论是否存在满足条件的元素配对，我们算法的时间复杂度都是O(n)。我们看看相应的代码实现：
public class FindPairInAbsoluteSortedArray { private int[] sortedArray; private int indexI; private int indexJ; private boolean bSuccessed = false; private int k ; public FindPairInAbsoluteSortedArray(int[] sortedArray, int k) { this.sortedArray = sortedArray; this.indexI = -1; this.indexJ = -1; this.k = k; } private void findPairWithSameSign(boolean positive) { /* * 如果满足条件的元素对都是正数或负数的话，那么用i指向第一个正数或负数，j指向最后一个整数或负数， * 如果两元素都是正数，如果A[i] A[j] == k，算法结束，如果A[i] A[j] > k, 那么j--； * 如果A[i] A[j] < k，那么i * * 如果两元素都是负数，A[i] A[j] == k 算法结束，如果A[i] A[j]>k, 那么i ,直到下一个负数 * 如果A[i] A[j] < k ，那么j-- 直到下一个负数 */ int i = 0, j = this.sortedArray.length - 1; if (positive == true) { while (this.sortedArray[i] < 0) { i ; } while (this.sortedArray[j] < 0) { j--; } } else { while (this.sortedArray[i] > 0) { i ; } while (this.sortedArray[j] > 0) { j--; } } do { if (this.sortedArray[i] this.sortedArray[j] == this.k) { this.bSuccessed = true; this.indexI = i; this.indexJ = j; break; } if (this.sortedArray[i] this.sortedArray[j] < this.k) { if (positive == true) { i ; while (i < this.sortedArray.length && this.sortedArray[i] < 0) { i ; } } else { j--; while (j > 0 && this.sortedArray[j] > 0) { j--; } } }else { if (positive == true) { j--; while (i < this.sortedArray.length && this.sortedArray[j] < 0) { j--; } } else { i ; while (i < this.sortedArray.length && this.sortedArray[i] > 0) { i ; } } } }while (i < j); } private void findPairWithDifferentSign() { /* * 把i指向最后一个正数，把j指向最后一个负数，如果A[i] A[j] == k, 算法结束 * 如果A[i] A[j] < k，那么j--; * 如果A[i] A[j] > k , 那么k-- */ int i = this.sortedArray.length-1; int j = this.sortedArray.length-1; while (this.sortedArray[i] < 0 && i > 0) { i--; } while (this.sortedArray[j] > 0 && j > 0) { j--; } do { if (this.sortedArray[i] this.sortedArray[j] == this.k) { this.indexI = i; this.indexJ = j; this.bSuccessed = true; break; } if (this.sortedArray[i] this.sortedArray[j] > k) { i--; while (i > 0 && this.sortedArray[i] < 0) { i--; } } else { j--; while (j > 0 && this.sortedArray[j] > 0) { j--; } } }while(i > 0 && j > 0); } public void findPair() { this.findPairWithSameSign(true); if (this.bSuccessed == false) { this.findPairWithSameSign(false); } if (this.bSuccessed == false) { this.findPairWithDifferentSign(); } if (this.bSuccessed == false) { System.out.println("No such pair exist in array"); } else { System.out.println("The index are " this.indexI " and " this.indexJ " with value of " this.sortedArray[this.indexI] " and " this.sortedArray[this.indexJ]); } } }
类FindPairInAbsoluteSortedArray用于在绝对值排序的数组中查找满足条件的元素配对，它先根据两元素都是正数的情况下查找，然后再根据两元素都是负数的情况下查找，如果这两种情况都找不到，再尝试两元素一正一负的情况下查找，如果三种情况都找不到满足条件的元素，那么这样的元素在数组中不存在。
我们看看入口代码：
public class Searching { public static void main(String[] args) { int[] A = {-49, 75, 103, -147, 164, -197, -238, 314, 348, -422}; int k = 167; FindPairInAbsoluteSortedArray fi = new FindPairInAbsoluteSortedArray(A, k); fi.findPair(); } }
上面代码运行结果如下：
从运行结果上看，我们算法的实现是正确的，并且这种做法比原先依靠折半查找的效率要高，它的算法复杂度为O(n)，空间复杂度为O(1)。
