# 算法：支持重复元素的二分查找

``` 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)) {
13                             } else break;
14                         }
15                     }
16                 }
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)) {
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) {
13                             } else break;
14                         }
15                     }
16                 }
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) {
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     }```

``` 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 }```

```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>();
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));```

binarySearch4 => [3, 4]

0 条评论

## 相关文章

### sscanf的高级用法 正则表达式

sscanf() - 从一个字符串中读进与指定格式相符的数据。 函数原型: int sscanf( const char *, const char *, ....

5504

### C++11——对象移动与右值引用

C++11新标准中一个最主要的特性就是提供了移动而非拷贝对象的能力。如此做的好处就是，在某些情况下，对象拷贝后就立即被销毁了，此时如果移动而非拷贝对象会大幅提升...

842

2342

761

### Java开发者易犯错误Top10

Arrays.asList()将返回一个数组内部是私有静态类的ArrayList，这不是java.util.ArrayList类，java.util.Array...

1214

1759

1267

2408

### 《笨办法学Python》 第5课手记

《笨办法学Python》 第5课手记 本节内容复习了前两节的内容，并且引入了格式化字符，这节课里的格式化字符与C语言格式化字符，规则没有什么区别。 我把原文代码...

2589

2787