一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1656|回复: 7
收起左侧

[二分/排序/搜索] 求Binary search实现样板

[复制链接] |试试Instant~ |关注本帖
kinggarden2001 发表于 2016-1-25 09:03:38 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
我记得哪位大神分享过一个实现bianry search的样板,里面还有好几个例子。找不到了,不知道哪位知道那个模板的,请分享一下。谢谢。
beer 发表于 2016-1-27 04:45:49 | 显示全部楼层
  1. class BinarySearch {

  2.     // general binary search, cannot detect equality
  3.     private static int binarySearch(int[] arr, int target){
  4.         int lo = 0;
  5.         int hi = arr.length - 1;
  6.       
  7.         while(lo <= hi){
  8.             int mid = lo + (hi - lo) / 2;

  9.             if(arr[mid] < target) lo = mid + 1;
  10.             else if(arr[mid] > target) hi = mid - 1;
  11.             else return mid;
  12.         }
  13.         return -1;
  14.     }

  15.     // deferred binary search, can detect equality, return lo
  16.     private static int binarySearch2(int[] arr, int target){
  17.         int lo = 0;
  18.         int hi = arr.length - 1;
  19.         
  20.         while(lo <= hi){
  21.             int mid = lo + (hi - lo) / 2;

  22.             if(arr[mid] < target) lo = mid + 1;
  23.             else hi = mid - 1;
  24.         }

  25.         //no need deferred test for equality
  26.         // if((lo == hi) && (arr[lo] == target)) return lo;
  27.         return lo;
  28.     }

  29.     /**
  30.      * http://www.jiuzhang.com/solutions/binary-search/
  31.      */
  32.     public static int binarySearch3(int[] arr, int target) {
  33.         int lo = 0, hi = arr.length - 1;
  34.         
  35.         while (lo + 1 < hi) {
  36.             int mid = lo + (hi - lo) / 2;
  37.             if (arr[mid] < target) {
  38.                 lo = mid;
  39.             } else {
  40.                 hi = mid;
  41.             }
  42.         }
  43.         
  44.         // System.out.println(lo + " - " + hi);
  45.         if (arr[lo] == target) return lo;
  46.         if (arr[hi] == target) return hi;
  47.         return -1;
  48.     }


  49.     public static void main(String[] args){
  50.         int[] arr = {1, 2, 2, 2, 3, 4, 5};
  51.         int target = 2;
  52.         System.out.println("Target's location: " + binarySearch(arr, target));

  53.         System.out.println("Target's location: " + binarySearch2(arr, target));

  54.         System.out.println("Target's location: " + binarySearch3(arr, target));
  55.     }
  56. }
复制代码
回复 支持 1 反对 0

使用道具 举报

JamesJi 发表于 2016-1-25 09:57:56 | 显示全部楼层
这个网上一搜多得很吧?
回复 支持 反对

使用道具 举报

大眼珠子 发表于 2016-1-25 14:58:02 | 显示全部楼层
google一把
http://taop.marchtea.com/04.01.html
回复 支持 反对

使用道具 举报

 楼主| kinggarden2001 发表于 2016-1-26 03:16:33 | 显示全部楼层
一亩三分地严打"顶""好贴""收藏了"之类的垃圾回复帖!被警告三次,系统会自动封杀ID!

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

使用道具 举报

 楼主| kinggarden2001 发表于 2016-1-26 03:18:43 | 显示全部楼层
这个不是我想找的那个。那个搞了一个通用模板,可以解决duplicate的问题,而且可以在存在duplicate的情况下,稍加改变就可以找最小或者最大的index,就是search range。不过谢谢了,这个也不错。
回复 支持 反对

使用道具 举报

slaink 发表于 2016-1-26 04:17:57 | 显示全部楼层
http://bxshi.github.io/2015/08/18/Algorithm-Problems-Binary-Search/

我之前自己写的总结,不过没写完……差rotated的binary search
回复 支持 反对

使用道具 举报

iker01 发表于 2016-1-27 03:00:01 | 显示全部楼层
http://www.shuatiblog.com/blog/2014/06/08/NineChap-Binary-Search/
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-11 06:46

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表