二分（相关部分）

  1 /**
  2  * 1.普通二分（递归 && 非递归）
  3  * 2.包含重复元素的二分（第一个 && 最后一个）
  4  * 
  5  * @author wzl
  6  * @since 2020-10-07
  7  */
  8 public class 二分相关 {
  9     /**
 10      * 普通二分非递归
 11      */
 12     public static int binarySearch_unRecursion(int[] array, int target) {
 13         if (array == null || array.length == 0) {
 14             return -1;
 15         }
 16         int left = 0;
 17         int right = array.length - 1;
 18         while (left <= right) {
 19             int mid = (left + right) / 2;
 20             if (target == array[mid]) {
 21                 return target;
 22             } else if (target > array[mid]) {
 23                 left = mid + 1;
 24             } else {
 25                 right = mid - 1;
 26             }
 27         }
 28         System.out.println(left + " " + right);
 29         return -1;
 30     }
 31     
 32     /**
 33      * 普通二分递归
 34      */
 35     public static int binarySearch_recursion(int[] array, int target, int left, int right) {
 36         if (array == null || array.length == 0) {
 37             return -1;
 38         }
 39         if (left <= right) {
 40             int mid = (left + right) / 2;
 41             if (target == array[mid]) {
 42                 return target;
 43             } else if (target > array[mid]) {
 44                 return binarySearch_recursion(array, target, mid + 1, right);
 45             } else {
 46                 return binarySearch_recursion(array, target, left, mid - 1);
 47             }
 48         }
 49         return -1;
 50     }
 51     
 52     /**
 53      * 重复元素二分，第一个重复元素
 54      * 找target - 0.5，最后判断left标志位
 55      */
 56     public static int binarySearch_repeatFirst(int[] arr, int target) {
 57         if (arr == null || arr.length < 0) {
 58             return -1;
 59         }
 60         double t = target - 0.5;
 61         int left = 0;
 62         int right = arr.length - 1;
 63         while (left <= right) {
 64             int mid = (left + right) / 2;
 65             if (t > arr[mid]) {
 66                 left = mid + 1;
 67             } 
 68             if (t < arr[mid]) {
 69                 right = mid - 1;
 70             }
 71         }
 72         if (left >= 0 && left <= arr.length - 1 && arr[left] == target) {
 73             return left;
 74         }
 75         return -1;
 76     }
 77     
 78     /**
 79      * 重复元素二分，最后一个重复元素
 80      * 找target + 0.5, 最后判断 right标志位
 81      */
 82     public static int binarySearch_repeatLast(int[] arr, int target) {
 83         if (arr == null || arr.length < 0) {
 84             return -1;
 85         }
 86         double t = target + 0.5;
 87         int left = 0;
 88         int right = arr.length - 1;
 89         while (left <= right) {
 90             int mid = (left + right) / 2;
 91             if (t > arr[mid]) {
 92                 left = mid + 1;
 93             } 
 94             if (t < arr[mid]) {
 95                 right = mid - 1;
 96             }
 97         }
 98         if (right >= 0 && right <= arr.length - 1 && arr[right] == target) {
 99             return right;
100         }
101         return -1;
102     }
103     public static void main(String[] args) {
104         int[] arr = {1, 1, 1, 1};
105         System.out.println();
106     }
107 }