代码如下,其他的不多叙述,看注释即可
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 |
/** * 二分查找两种写法 */ package array; import java.util.Arrays; /** * * @author lizhongfeng_李忠峰 * @fileinfo Test array ArrayDemo.java * @time 2015年9月12日 */ public class ArrayDemo { /** * @param args */ public static void main(String[] args) { // TODO Auto-generated method stub int[] arr = { 13, 15, 19, 28, 33, 45, 78, 106 }; System.out.println(halfSearch(arr, 33)); System.out.println(halfSearch2(arr, 33)); System.out.println(insert(arr, 5)); System.out.println(Arrays.binarySearch(arr, 33));// 使用java内置函数查找,不存在时返回的num= -插入位置-1 } // 写法① // 先判断中间值是不是key,如果不是再和中间值比较,循环知道找到或者循环结束; public static int halfSearch(int[] arr, int key) { int max, min, mid; min = 0; max = arr.length - 1; mid = (max + min) / 2; // 循环判断要用到,所以要先计算,方法②用不到,可以直接写在循环里面; while (arr[mid] != key) { if (key > arr[mid]) { min = mid + 1; } else if (key < arr[mid]) { max = mid - 1; } if (max < min) { return -1; } mid = (min + max) / 2; } return mid; } // 写法② // 先判断小的角标是不是比大的角标大,如果大,说明已经循环结束了。 public static int halfSearch2(int[] arr, int key) { int min, max, mid; min = 0; max = arr.length - 1; while (min <= max) { mid = (min + max) / 2; if (key > arr[mid]) { min = mid + 1; } else if (key < arr[mid]) { max = mid - 1; } else { return mid; } } return -1; } // 插入一个值时,大小序时应该插入的位置 public static int insert(int[] arr, int key) { int min, max, mid; min = 0; max = arr.length - 1; while (min <= max) { mid = (min + max) / 2; if (key > arr[mid]) { min = mid + 1; } else if (key < arr[mid]) { max = mid - 1; } else { return mid; } } return min; } } |
Comments | NOTHING