求Binary search实现样板

我记得哪位大神分享过一个实现bianry search的样板，里面还有好几个例子。找不到了，不知道哪位知道那个模板的，请分享一下。谢谢。

1. class BinarySearch {
   
2. 
   
3.     // general binary search, cannot detect equality
   
4.     private static int binarySearch(int[] arr, int target){
   
5.         int lo = 0;
   
6.         int hi = arr.length - 1;
   
7.       
   
8.         while(lo <= hi){
   
9.             int mid = lo + (hi - lo) / 2;
   
10. 
    
11.             if(arr[mid] < target) lo = mid + 1;
    
12.             else if(arr[mid] > target) hi = mid - 1;
    
13.             else return mid;
    
14.         }
    
15.         return -1;
    
16.     }
    
17. 
    
18.     // deferred binary search, can detect equality, return lo
    
19.     private static int binarySearch2(int[] arr, int target){
    
20.         int lo = 0;
    
21.         int hi = arr.length - 1;
    
22.         
    
23.         while(lo <= hi){
    
24.             int mid = lo + (hi - lo) / 2;
    
25. 
    
26.             if(arr[mid] < target) lo = mid + 1;
    
27.             else hi = mid - 1;
    
28.         }
    
29. 
    
30.         //no need deferred test for equality
    
31.         // if((lo == hi) && (arr[lo] == target)) return lo;
    
32.         return lo;
    
33.     }
    
34. 
    
35.     /**
    
36.      * http://www.jiuzhang.com/solutions/binary-search/
    
37.      */
    
38.     public static int binarySearch3(int[] arr, int target) {
    
39.         int lo = 0, hi = arr.length - 1;
    
40.         
    
41.         while (lo + 1 < hi) {
    
42.             int mid = lo + (hi - lo) / 2;
    
43.             if (arr[mid] < target) {
    
44.                 lo = mid;
    
45.             } else {
    
46.                 hi = mid;
    
47.             }
    
48.         }
    
49.         
    
50.         // System.out.println(lo + " - " + hi);
    
51.         if (arr[lo] == target) return lo;
    
52.         if (arr[hi] == target) return hi;
    
53.         return -1;
    
54.     }
    
55. 
    
56. 
    
57.     public static void main(String[] args){
    
58.         int[] arr = {1, 2, 2, 2, 3, 4, 5};
    
59.         int target = 2;
    
60.         System.out.println("Target's location: " + binarySearch(arr, target));
    
61. 
    
62.         System.out.println("Target's location: " + binarySearch2(arr, target));
    
63. 
    
64.         System.out.println("Target's location: " + binarySearch3(arr, target));
    
65.     }
    
66. }
    

复制代码

这个网上一搜多得很吧？

google一把
http://taop.marchtea.com/04.01.html

一亩三分地严打"顶""好贴""收藏了"之类的垃圾回复帖！被警告三次，系统会自动封杀ID！

想支持楼主，请点击帖子下方的"好苗""分享""收藏"键，酌情给楼主加大米（系统不扣你自己的分）。
积分不够看不了帖子，请参考论坛导航里的"帮助"，"新手提纲"里有攒积分指南

这个不是我想找的那个。那个搞了一个通用模板，可以解决duplicate的问题，而且可以在存在duplicate的情况下，稍加改变就可以找最小或者最大的index，就是search range。不过谢谢了，这个也不错。

http://bxshi.github.io/2015/08/18/Algorithm-Problems-Binary-Search/

我之前自己写的总结，不过没写完……差rotated的binary search

http://www.shuatiblog.com/blog/2014/06/08/NineChap-Binary-Search/