算法：支持重復元素的二分查找 - yjmyzz－IT工程師數位筆記本

文章出處

近幾天在處理的一個項目，需要頻繁對一些有序超大集合進行目標查找，二分查找算法是這類問題的最優解。但是java的Arrays.binarySearch()方法，如果集合中有重復元素，而且遇到目標元素正好是這些重復元素之一，該方法只能返回一個，并不能將所有的重復目標元素都返回，沒辦法，只能自造輪子了。

先復習下二分查找的經典算法：

 1     private int binarySearch1(Integer[] A, Integer x) {
 2         int low = 0, high = A.length - 1;
 3         while (low <= high) {
 4             int mid = (low + high) / 2;
 5             if (A[mid].equals(x)) {
 6                 return mid;
 7             } else if (x < A[mid]) {
 8                 high = mid - 1;
 9             } else {
10                 low = mid + 1;
11             }
12         }
13         return -1;
14     }

思路很簡單，先定位到中間元素，如果中間元素比目標元素大，則扔掉后一半，反之扔掉前一半，如果正好一次命中，直接返回。

略做改進：

 1     private List<Integer> binarySearch2(Integer[] A, Integer x) {
 2         List<Integer> result = new ArrayList<Integer>();
 3         int low = 0, high = A.length - 1;
 4         while (low <= high) {
 5             int mid = (low + high) / 2;
 6             if (A[mid].equals(x)) {
 7                 if (mid > 0) {
 8                     //看前一個元素是否＝目標元素
 9                     if (A[mid - 1].equals(x)) {
10                         for (int i = mid - 1; i >= 0; i--) {
11                             if (A[i].equals(x)) {
12                                 result.add(i);
13                             } else break;
14                         }
15                     }
16                 }
17                 result.add(x);
18                 if (mid < high) {
19                     //看后一個元素是否＝目標元素
20                     if (A[mid + 1].equals(x)) {
21                         for (int i = mid + 1; i <= high; i++) {
22                             if (A[i].equals(x)) {
23                                 result.add(i);
24                             } else break;
25                         }
26                     }
27                 }
28                 return result;
29             } else if (x < A[mid]) {
30                 high = mid - 1;
31             } else {
32                 low = mid + 1;
33             }
34         }
35         return result;
36 
37     }

思路：命中目標后，看下前一個緊挨著的元素是否也是要找的元素，如果是，則順著向前取，直到遇到不等于目標元素為止。然后再看后一個緊挨著的元素，做類似處理。

測試：

1         Integer[] A = new Integer[]{1, 2, 3, 4, 5, 5, 5, 6, 7, 8, 9};
2 
3         System.out.println("binarySearch1 => ");
4         System.out.println(binarySearch1(A, 5));
5 
6         System.out.println("binarySearch2 => ");
7         System.out.println(binarySearch2(A, 5));

binarySearch1 =>
5
binarySearch2 =>
[4, 5, 6]

從返回的下標值看，都在預期之中，但是事情并未到此止步，通常要查找的列表元素，并不是數值這么簡單，一般是一些復雜的對象實例，為了做到通用，得弄成一個泛型版本：

 1    private <T> List<Integer> binarySearch4(List<T> A, T x, Comparator<? super T> comparator) {
 2         List<Integer> result = new ArrayList<Integer>();
 3         int low = 0, high = A.size() - 1;
 4         while (low <= high) {
 5             int mid = (low + high) / 2;
 6             int temp = comparator.compare(x, A.get(mid));
 7             if (temp == 0) {
 8                 if (mid > 0) {
 9                     if (comparator.compare(x, A.get(mid - 1)) == 0) {
10                         for (int i = mid - 1; i >= 0; i--) {
11                             if (comparator.compare(A.get(i), x) == 0) {
12                                 result.add(i);
13                             } else break;
14                         }
15                     }
16                 }
17                 result.add(mid);
18                 if (mid < high) {
19                     if (comparator.compare(x, A.get(mid + 1)) == 0) {
20                         for (int i = mid + 1; i <= high; i++) {
21                             if (comparator.compare(x, A.get(i)) == 0) {
22                                 result.add(i);
23                             } else break;
24                         }
25                     }
26                 }
27                 return result;
28 
29             } else if (temp < 0) {
30                 high = mid - 1;
31             } else {
32                 low = mid + 1;
33             }
34         }
35 
36         return result;
37     }

為了比較二個復雜對象實例的大小，引入了Comparator接口，可以根據業務需要，則調用者自定義比較規則。

測試一下：

先定義一個業務對象類AwbDto:

 1 package com.cnblogs.yjmyzz.test.domain;
 2 
 3 /**
 4  * Created by jimmy on 15/1/8.
 5  */
 6 public class AwbDto {
 7 
 8 
 9     /**
10      * 運單號
11      */
12     private String awbNumber;
13 
14     /**
15      * 始發站
16      */
17     private String originAirport;
18 
19     public AwbDto(String awbNumber, String originAirport) {
20         this.awbNumber = awbNumber;
21         this.originAirport = originAirport;
22     }
23 
24     public String getAwbNumber() {
25         return awbNumber;
26     }
27 
28     public void setAwbNumber(String awbNumber) {
29         this.awbNumber = awbNumber;
30     }
31 
32     public String getOriginAirport() {
33         return originAirport;
34     }
35 
36     public void setOriginAirport(String originAirport) {
37         this.originAirport = originAirport;
38     }
39 }

還需要定義AwbData比較大小的業務規則，假設：只要運單號相同，則認為相等（即：用運單號來區分對象大小）

1     private class AwbDtoComparator implements Comparator<AwbDto> {
2 
3         @Override
4         public int compare(AwbDto x, AwbDto y) {
5             return x.getAwbNumber().compareTo(y.getAwbNumber());
6         }
7     }

測試代碼：

 1         List<AwbDto> awbList = new ArrayList<AwbDto>();
 2         awbList.add(new AwbDto("112-10010011", "北京"));
 3         awbList.add(new AwbDto("112-10010022", "上海"));
 4         awbList.add(new AwbDto("112-10010033", "天津"));
 5         awbList.add(new AwbDto("112-10010044", "武漢"));
 6         awbList.add(new AwbDto("112-10010044", "武漢"));
 7         awbList.add(new AwbDto("112-10010055", "廣州"));
 8 
 9         AwbDtoComparator comparator = new AwbDtoComparator();
10 
11         AwbDto x = new AwbDto("112-10010044", "武漢");
12 
13 
14         System.out.println("binarySearch4 => ");
15         System.out.println(binarySearch4(awbList, x, comparator));