33.二分查找在旋转数组

题目描述

给你一个整数数组 nums ，和一个整数 target 。 该整数数组原本是按升序排列，但输入时在预先未知的某个点上进行了旋转。（例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] ）。 请你在数组中搜索 target ，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。 示例 1： 输入：nums = [4,5,6,7,0,1,2], target = 0输出：4示例 2： 输入：nums = [4,5,6,7,0,1,2], target = 3输出：-1示例 3： 输入：nums = [1], target = 0输出：-1

code1:

  1. static int SearchInRotatedSortedArray(int array[], int low, int high, int target) {
  2.         if (array.length == 0) return -1;
  3.         if (array.length == 1) return array[0] == target ? 0 : -1;
  4.         int p = findT(array);
  5.         if (p == -1) {
  6.             p = findP(array, 0, array.length - 1, target);
  7.         } else if (array[0] <= target) {
  8.             p = findP(array, 0, p, target);
  9.         } else {
  10.             p = findP(array, p + 1, array.length - 1, target);
  11.         }
  12.         return array[p] == target ? p : -1;
  13.     }
  14.     static int findP(int[] nums, int l, int h, int t) {
  15.         int m = 0;
  16.         while (l < h) {
  17.             m = l + (h - l) / 2; //中间数
  18.             if (nums[m] < t) {
  19.                 l = m + 1;
  20.             } else {
  21.                 h = m;
  22.             }
  23.         }
  24.         return l;
  25.     }
  26.     static int findT(int[] nums) {
  27.         if (nums[0] < nums[nums.length - 1]) return -1;
  28.         int l = 0, h = nums.length - 1, m = 0;
  29.         while (l < h) {
  30.             m = l + (h - l + 1) / 2;
  31.             if (nums[m] < nums[0]) {
  32.                 h = m - 1;
  33.             } else {
  34.                 l = m;
  35.             }
  36.         }
  37.         return l;
  38.     }

code2:

首先进行查找，找到旋转的位置，然后根据那个位置分成两部分，进行二分查找

  1. //进行两次二分查找，
  2.     static int SearchInRotatedSortedArray(int array[], int low, int high, int target) {
  3.         if (array == null || array.length == 0) {
  4.             return -1;
  5.         }
  6.         if(array.length==1) return array[0] == target ? 0 : -1;
  7.         //首先进行查找变化值, 然后根据两部分进行二分查找
  8.         int cutoff = 0;
  9.         for (int i = 0; i < array.length-1; i++) {
  10.             if(array[i] > array[i+1] ){
  11.                 cutoff=i;
  12.                 break;
  13.             }
  14.         }
  15.         //进行二分查找
  16.         int left = binarySearch(array, 0, cutoff, target);
  17.         int right = binarySearch(array, cutoff+1, array.length-1, target);
  18.         return left == -1 ? right : left;
  19.     }
  20.     //进行二分查找
  21.     static int binarySearch(int[] arr, int left, int right, int target) {
  22.         while (left <= right) { //二分朝招
  23.             int mid = left - (left-right) /2;
  24.             if (arr[mid] == target) { //等于target
  25.                 return mid;
  26.             }else if(arr[mid] > target){
  27.                 right = mid -1;
  28.             }else{
  29.                 left= mid+1;
  30.             }
  31.         }
  32.         return -1;
  33.     }

code3:

  1. public static void main(String[] args) {
  2.         int[] arr = {4,5,6,7,0,1,2};
  3.         System.out.println(search(arr,  0));
  4.     }
  5.     //进行两次二分查找
  6.     //肯定是有一边是有序的
  7.     static  public int search(int[] nums, int target) {
  8.         int n = nums.length; //获取数组的长度
  9.         if (n == 0) { //如果数组长度为0 ，直接返回
  10.             return -1;
  11.         }
  12.         if (n == 1) { //如果长度为1 ，只有一个值，判断这个值和target是否相同，如果不相同返回-1
  13.             return nums[0] == target ? 0 : -1;
  14.         }
  15.         //left right左右两个值
  16.         int l = 0, r = n - 1;
  17.         while (l <= r) { //左边小于右边
  18.             int mid = (l + r) / 2;
  19.             if (nums[mid] == target) { //中间值正好找到
  20.                 return mid;
  21.             }
  22.             //wyg 判断哪个是有序的一边
  23.             if (nums[0] <= nums[mid]) { //左边是有序的一侧
  24.                 if (nums[0] <= target && target < nums[mid]) {//左边
  25.                     r = mid - 1; //左边
  26.                 } else { //右边
  27.                     l = mid + 1;
  28.                 }
  29.             } else { //右边是有序的
  30.                 if (nums[mid] < target && target <= nums[n - 1]) {
  31.                     l = mid + 1;
  32.                 } else {
  33.                     r = mid - 1;
  34.                 }
  35.             }
  36.         }
  37.         return -1;
  38.     }