LeetCode33. 搜索旋转排序数组-Java&Go-二分查找，妙

• 算法
  • 1.二分查找找到最小值的位置
  • 2.利用这一位置，再次进行二分查找
    • 每次计算middle之后，需要再计算该middle位置对应数组在旋转前的元素是谁
    • realMiddle = (middle + minIndex) % nums.length;

public int search(int[] nums, int target) {
    int start = 0, end = nums.length - 1;
    while (start < end) {
        int middle = (start + end) >> 1;
        if (nums[middle] < nums[end]) {
            end = middle;
        } else {
            start = middle + 1;
        }
    }

    int minIndex = start;
    start = 0;
    end = nums.length - 1;
    while (start <= end) {
        int middle = (start + end) >> 1;
        int realMiddle = (middle + minIndex) % nums.length;
        if (nums[realMiddle] == target) {
            return realMiddle;
        } else if (nums[realMiddle] > target) {
            end = middle - 1;
        } else {
            start = middle + 1;
        }
    }
    return -1;
}

func search(nums []int, target int) int {
    n := len(nums)
    start, end := 0, n - 1
    for start < end {
        middle := (start + end) >> 1
        if nums[middle] < nums[end] {
            end = middle
        } else {
            start = middle + 1
        }
    }

    minIndex, start, end := start, 0, n - 1
    for start <= end {
        middle := (start + end) >> 1
        realMiddle := (middle + minIndex) % n
        if (nums[realMiddle] == target) {
            return realMiddle
        } else if (nums[realMiddle] < target) {
            start = middle + 1
        } else {
            end = middle - 1
        }
    }
    return -1
}

• 算法
  • 1.二分查找找到最小值的位置
  • 2.利用这一位置，将目标值和数组最后一个值比较，确定目标值所在的有序的那一半子数组范围
  • 3.在子数组范围进行二分查找

public int search(int[] nums, int target) {
    int n = nums.length;
    int start = 0, end = n - 1;
    while (start < end) {
        int middle = (start + end) >> 1;
        if (nums[middle] < nums[end]) {
            end = middle;
        } else {
            start = middle + 1;
        }
    }

    int minIndex = start;
    start = (target <= nums[n-1]) ? minIndex : 0;
    end = (target > nums[n-1]) ? minIndex - 1 : n - 1;
    while (start <= end) {
        int middle = (start + end) >> 1;
        if (nums[middle] == target) {
            return middle;
        } else if (nums[middle] > target) {
            end = middle - 1;
        } else {
            start = middle + 1;
        }
    }
    return -1;
}

func search(nums []int, target int) int {
    n := len(nums)
    start, end := 0, n - 1
    for start < end {
        middle := (start + end) >> 1
        if nums[middle] < nums[end] {
            end = middle
        } else {
            start = middle + 1
        }
    }

    minIndex := start
    if target <= nums[n-1] {
        start, end = minIndex, n - 1
    } else {
        start, end = 0, minIndex - 1
    }
    for start <= end {
        middle := (start + end) >> 1
        if (nums[middle] == target) {
            return middle
        } else if (nums[middle] < target) {
            start = middle + 1
        } else {
            end = middle - 1
        }
    }
    return -1
}