平移数组ShiftedNumber查找

平移数组ShiftedNumber查找

平移数组

• 普通数据
  int[] arr = {0, 1, 2, 3, 4, 5, 5, 5, 8, 9};

• 平移数组

  int[] arr = {8, 9,0, 1, 2, 3, 4, 5, 6, 7 };

查找平移位数

查旋转平移位数，
即查找 最小值的 index
认定 >= head 的为Blue
right就是要找的值
注意边界情况

二分查找

    /*** 旋转数组，找平移位数* ps：不适合有重复数据的* eg: 222122* or: 23222* or: 2345612** @param arr* @return*/public static int shiftSearch(int[] arr) {int left = -1;int right = arr.length;if (right < 2) {return 0;}int head = arr[0];if (arr[left + 1] < arr[right - 1]) {return 0;}while (left + 1 != right) {int mid = (left + right) / 2;if (arr[mid] >= head) {left = mid;} else {right = mid;}}return right;}

查找指定数据

升序数组，查找指定数据
二分查找，注意blue条件

    /*** 旋转数组，找指定值的下标** @param arr* @param target* @return*/public static int shiftSearchNum(int[] arr, int target) {int left = -1;int right = arr.length;int head = arr[0];while (left + 1 != right) {int mid = (left + right) / 2;if (target == arr[mid]) {return mid;}if (target > arr[mid] && arr[mid] > head ||arr[mid] > head && head > target ||head > target && target > arr[mid]) {left = mid;} else {right = mid;}}return left;}

牛刀小试

    public static void main(String[] args) {int[] shiftArr = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};Assert.isTrue(shiftSearch(shiftArr) == 0, "查找平移位数");Assert.isTrue(shiftSearchNum(shiftArr, 0) == 0, "查找数据");shiftArr = new int[]{8, 9, 0, 1, 2, 3, 4, 5, 6, 7};Assert.isTrue(shiftSearch(shiftArr) == 2, "查找平移位数");Assert.isTrue(shiftSearchNum(shiftArr, 0) == 2, "查找数据");shiftArr = new int[]{7, 8, 9, 0, 1, 2, 3, 4, 5, 6};Assert.isTrue(shiftSearch(shiftArr) == 3, "查找平移位数");Assert.isTrue(shiftSearchNum(shiftArr, 5) == 8, "查找数据");shiftArr = new int[]{7, 8, 9, 10, 1, 2, 3, 4, 5, 6};Assert.isTrue(shiftSearch(shiftArr) == 4, "查找平移位数");Assert.isTrue(shiftSearchNum(shiftArr, 10) == 3, "查找数据");shiftArr = new int[]{5};Assert.isTrue(shiftSearch(shiftArr) == 0, "查找平移位数");Assert.isTrue(shiftSearchNum(shiftArr, 5) == 0, "查找数据");}

reference