實現二分法查找
二分法查找，需要數組內是一個有序的序列二分查找比線性查找：數組的元素數越多，效率提高的越明顯二分查找的效率表示：O(log2N) N在2的M次冪範圍，那查找的次數最大就是M, log2N表示2的M次冪等於N, 省略常數，簡寫成O(logN)
如有一個200個元素的有序數組，那麼二分查找的最大次數：
2^7=128, 2^8=256, 可以看出7次冪達不到200，8次冪包括， 所以最大查找次數就等於8
//循環，二分查找static int binarySearch(int[] array, int data) { int start = 0; int end = array.length - 1; int mid = -1; while (start <= end) { System.out.println("查找次數"); mid = (start + end) >>> 1; if (array[mid] < data) { start = mid + 1; } else if (array[mid] > data) { end = mid - 1; } else { return mid; } System.out.println("start=" + start+",end="+end+",mid="+mid); } return -1; } //遞歸二分查找初始start=0, end = array.length - 1 static int binarySearch4Recursion(int[] array, int data, int start, int end) { int mid = -1; System.out.println("查找次數"); if (start > end) { return mid; } mid = (start + end) >>> 1; if (array[mid] < data) { return binarySearch4Recursion(array, data, mid + 1, end); } else if (array[mid] > data) { return binarySearch4Recursion(array, data, start, mid - 1); } else { return mid; } }二分法插入排序
設有一個序列a[0],a[1]...a[n];其中a[i-1]前是已經有序的,當插入時a[i]時,利用二分法搜索a[i]插入的位置效率：O(N^2)，對於初始基本有序的序列，效率上不如直接插入排序；對於隨機無序的序列，效率比直接插入排序要高
/* * 二分(折半)插入排序* 設有一個序列a[0],a[1]...a[n];其中a[i-1]前是已經有序的,當插入時a[i]時,利用二分法搜索a[i]插入的位置*/ public class BinaryInsertSort { public static void main(String[] args) { int len = 10; int[] ary = new int[len]; Random random = new Random(); for (int j = 0; j < len; j++) { ary[j] = random.nextInt(1000); } binaryInsert(ary); /* * 複雜度分析： 最佳情況，即都已經排好序，則無需右移，此時時間複雜度為：O(n lg n) 最差情況，全部逆序，此時復雜度為O(n^2) * 無法將最差情況的複雜度提升到O(n|logn)。 */ // 打印數組printArray(ary); } /** * 插入排序* @param ary */ private static void binaryInsert(int[] ary) { int setValueCount = 0; // 從數組第二個元素開始排序，因為第一個元素本身肯定是已經排好序的for (int j = 1; j < ary.length; j++) {// 複雜度n // 保存當前值int key = ary[j]; // ∆ 利用二分查找定位插入位置// int index = binarySearchAsc(ary, ary[j], 0, j - 1);// 複雜度：O(logn) // int index = binarySearchDesc(ary, ary[j], 0, j - 1);// 複雜度：O(logn) int index = binarySearchDesc2(ary, ary[j], 0, j - 1);// 複雜度：O(logn) printArray(ary); System.out.println("第" + j +"個索引上的元素要插入的位置是：" + index); // 將目標插入位置，同時右移目標位置右邊的元素for (int i = j; i > index; i--) {// 複雜度,最差情況：(n-1)+(n-2)+...+n/2=O(n^2) ary[i] = ary[i - 1]; //i-1 <==> index setValueCount++; } ary[index] = key; setValueCount++; } System.out.println("/n 設值次數(setValueCount)=====> " + setValueCount); } /** * 二分查找升序遞歸* * @param ary * 給定已排序的待查數組* @param target * 查找目標* @param from * 當前查找的範圍起點* @param to * 當前查找的返回終點* @return 返回目標在數組中，按順序應在的位置*/ private static int binarySearchAsc(int[] ary, int target, int from, int to) { int range = to - from; // 如果範圍大於0，即存在兩個以上的元素，則繼續拆分if (range > 0) { // 選定中間位int mid = (to + from) / 2; // 如果臨界位不滿足，則繼續二分查找if (ary[mid] > target) { /* * mid > target, 升序規則，target較小，應交換位置前置， 即target定位在mid位置上， * 根據查找思想， 從from到mid-1認為有序， 所以to=mid-1 */ return binarySearchAsc(ary, target, from, mid - 1); } else { /* * mid < target, 升序規則，target較大，不交換位置，查找比較的起始位置應為mid+1 */ return binarySearchAsc(ary, target, mid + 1, to); } } else { if (ary[from] > target) {//如5,4, 要插入的是4 return from; } else { return from + 1; } } } /** * 二分查找降序， 遞歸*/ private static int binarySearchDesc(int[] ary, int target, int from, int to) { int range = to - from; if (range > 0) { int mid = (from + to) >>> 1; if (ary[mid] > target) { return binarySearchDesc(ary, target, mid + 1, to); } else { return binarySearchDesc(ary, target, from, mid - 1); } } else { if (ary[from] > target) {//如5,4, 要插入的是4 return from + 1; } else { return from; } } } /** * 二分查找降序， 非遞歸*/ private static int binarySearchDesc2(int[] ary, int target, int from, int to) { // while(from < to) { for (; from < to; ) { int mid = (from + to) >>> 1; if (ary[mid] > target) { from = mid + 1; } else { to = mid -1; } } //from <==> to; if (ary[from] > target) {//如5,4, 要插入的是4 return from + 1; } else { return from; } } private static void printArray(int[] ary) { for (int i : ary) { System.out.print(i + " "); } } }列印
918 562 442 531 210 216 931 706 333 132 第1個索引上的元素要插入的位置是：1 918 562 442 531 210 216 931 706 333 132 第2個索引上的元素要插入的位置是：2 918 562 442 531 210 216 931 706 333 132 第3個索引上的元素要插入的位置是：2 918 562 531 442 210 216 931 706 333 132 第4個索引上的元素要插入的位置是：4 918 562 531 442 210 216 931 706 333 132 第5個索引上的元素要插入的位置是：4 918 562 531 442 216 210 931 706 333 132 第6個索引上的元素要插入的位置是：0 931 918 562 531 442 216 210 706 333 132 第7個索引上的元素要插入的位置是：2 931 918 706 562 531 442 216 210 333 132 第8個索引上的元素要插入的位置是：6 931 918 706 562 531 442 333 216 210 132 第9個索引上的元素要插入的位置是：9
設值次數(setValueCount)=====> 24
931 918 706 562 531 442 333 216 210 132