本文共 2946 字，大约阅读时间需要 9 分钟。

找旋转数组中的target

解法一：

1. 如果当前mid就是target，那么返回
2. 如果左边有序(nums[mid] > nums[beg]))那么就跳到3，否则是右边有序(nums[mid] < nums[beg])，就跳到四******都是用mid和beg比较！！！
3. 检查target是否在beg~mid之间，如果是end = mid - 1；否则beg = mid + 1
4. 检查target是否在mid~end之间，如果是beg = mid + 1；否则end = mid - 1

public class Solution {    public int search(int[] nums, int target) {        if (nums == null || nums.length == 0) {            return -1;        }        int beg = 0;        int end = nums.length - 1;        while (beg < end) {            int mid = beg + (end - beg) / 2;            if (nums[mid] == target) {                return mid;            } else if (nums[mid] >= nums[beg]) {                if (nums[mid] > target && target >= nums[beg]) {                    end = mid - 1;                } else {                    beg = mid + 1;                }            } else {                if (nums[mid] < target && nums[end] >= target) {                    beg = mid + 1;                } else {                    end = mid - 1;                }            }        }        return nums[beg] == target ? beg : -1;    }}

解法二：

找到最小值位置，然后二分查找target的时候，将mid重映射到未旋转前数组的位置

其中找最小值先找到旋转前前半个递增的子数组，所以是无脑 nums[mid] > nums[end] -- beg = mid + 1;

public class Solution {    public int search(int[] nums, int target) {        if (nums == null || nums.length == 0) {            return -1;        }        int beg = 0;        int end = nums.length - 1;        while (beg < end) {            int mid = beg + (end - beg) / 2;            if (nums[mid] > nums[end]) {                beg = mid + 1;            } else {                end = mid;            }        }        int rot = beg;        beg = 0;        end = nums.length - 1;        while (beg <= end) {            int mid = beg + (end - beg) / 2;            int realMid = (mid + rot) % nums.length;            if (nums[realMid] == target) {                return realMid;            } else if (nums[realMid] > target) {                end = mid - 1;            } else {                beg = mid + 1;            }        }        return -1;    }}

假如数组中存在重复数字呢？

public class Solution {    public boolean search(int[] nums, int target) {        if (nums == null || nums.length == 0) {            return false;        }        int beg = 0;        int end = nums.length - 1;        while (beg < end) {            int mid = beg + (end - beg) / 2;            if (nums[mid] == target) {                return true;            }            if (nums[mid] > nums[beg]) {                if (nums[mid] > target && target >= nums[beg]) {                    end = mid - 1;                } else {                    beg = mid + 1;                }            } else if (nums[mid] < nums[beg]) {                if (nums[mid] < target && nums[end] >= target) {                    beg = mid + 1;                } else {                    end = mid - 1;                }            } else {                beg++;            }        }        return nums[beg] == target;    }}

转载地址：http://svhld.baihongyu.com/