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
| package cn.joinhealth;
public class BisectionMethod {
public static void main(String[] args) { int[] array = {1, 3, 5, 6}; System.out.println("binarySearch: " + binarySearch(array, 5) + "\n"); System.out.println("binarySearch2: " + binarySearch2(array, 5) + "\n"); System.out.println("binarySearch3: " + binarySearch3(array, 5, 0, 3) + "\n"); }
public static int binarySearch(int[] nums, int target) { int len = nums.length; int left = 0, right = len - 1; while (left <= right) { int mid = (left + right) / 2; System.out.println("searchInsert left: " + left + ",right: " + right + ",mid: " + mid + ",nums[mid]: " + nums[mid]); if (nums[mid] <= target) { left = mid + 1; } else { right = mid - 1; } } return right; }
public static int binarySearch2(int[] nums, int target) { int len = nums.length; int left = 0, right = len; while (left < right) { int mid = (left + right) / 2; System.out.println("searchInsert2 left: " + left + ",right: " + right + ",mid: " + mid + ",nums[mid]: " + nums[mid]); if (nums[mid] < target) { left = mid + 1; } else { right = mid; } } return right; }
public static int binarySearch3(int[] nums, int target, int left, int right) { if (left > right) { return -1; } int mid = (left + right) / 2; System.out.println("searchInsert3 left: " + left + ",right: " + right + ",mid: " + mid + ",nums[mid]: " + nums[mid]); if (nums[mid] == target) { return mid; } else if (target < nums[mid]) { return binarySearch3(nums, target, left, mid - 1); } else { return binarySearch3(nums, target, mid + 1, right); } } }
|