浏览 1417 次
锁定老帖子 主题:小试 二分法
精华帖 (0) :: 良好帖 (0) :: 新手帖 (0) :: 隐藏帖 (0)
|
|
---|---|
作者 | 正文 |
发表时间:2011-04-15
最后修改:2011-04-15
public class FinderPosition { private static int findPositionInArray(int[] i, int target) { int cusor = 0, rangeStart = 0, rangeEnd = i.length, findCount = 0; while (true) { findCount++; if(target < i[rangeStart] || target > i[rangeEnd - 1]) { cusor = -1; break; } if (target == i[cusor]) break; cusor = (rangeEnd + rangeStart) / 2; if (i[cusor] > target) { rangeEnd = cusor; }else if (i[cusor] < target){ rangeStart = cusor; }else if (i[cusor] == target) { break; } } System.out.println("Found " + findCount +" times, the result is:" + cusor); return cusor; } public static void main(String[] args) { int[] i = { 20080130,20080131, 20080229, 20080331, 20080430, 20080530, 20080630, 20080731, 20080829, 20080901, 20080929, 20080930, 20081031, 20081128, 20081231, 20090101, 20090130, 20090227, 20090331, 20090401, 20090430, 20090501, 20090529, 20090630, 20090701, 20090731, 20090831, 20090901, 20090930, 20101014, 20101015, 20101020, 20101029, 20101031, 20101101, 20101111, 20101112, 20101114, 20101117, 20101119, 20101126, 20101129, 20101130, 20101201, 20101202, 20101203, 20101206, 20101207, 20101208, 20101209, 20101210, 20101213, 20101214, 20101215, 20101216, 20101217, 20101218, 20101220, 20101221, 20101222, 20101223, 20101224, 20101225, 20101227, 20101228, 20101230, 20101231, 20110101, 20110103, 20110104, 20110105, 20110106, 20110107, 20110110, 20110111, 20110112, 20110113, 20110114, 20110118, 20110119, 20110120, 20110121, 20110124, 20110125, 20110126, 20110126, 20110127, 20110201, 20110203, 20110207, 20110208, 20110210, 20110211, 20110214, 20110215, 20110216, 20110218, 20110221, 20110222, 20110223, 20110224, 20110225, 20110228, 20110301, 20110302, 20110303, 20110307, 20110308, 20110309, 20110310, 20110311, 20110315, 20110316, 20110317, 20110318, 20110323, 20110324, 20110325, 20110328, 20110329, 20110330, 20110404, 20110406, 20110407, 20110419, 20110420}; int target = 20110420; System.out.println("Begin to find: " + target); int position = findPositionInArray(i,target); if (position != -1) System.out.println("position " + position + " is: " + i[position]); } } 结果: Begin to find: 20110420 Found 7 times, the result is:125 position 125 is: 20110420 2的x方 <= i.length, 循环查找次数不会多于x次. 声明:ITeye文章版权属于作者,受法律保护。没有作者书面许可不得转载。
推荐链接
|
|
返回顶楼 | |