【算法】【线性表】搜索旋转排序数组（无重复数据）-526互联

1 题目

给定一个有序数组，但是数组以某个元素作为支点进行了旋转(比如，0 1 2 4 5 6 7 可能成为4 5 6 7 0 1 2)。给定一个目标值target进行搜索，如果在数组中找到目标值返回数组中的索引位置，否则返回-1。你可以假设数组中不存在重复的元素。

样例 1：

输入：

数组 = [4, 5, 1, 2, 3]
target = 1

输出：

解释：1在数组中对应索引位置为2。

样例 2：

输入：

数组 = [4, 5, 1, 2, 3]
target = 0

输出：

-1

解释：0不在数组中，返回-1。

2 解答

public class Solution {
    /**
     * @param a: an integer rotated sorted array
     * @param target: an integer to be searched
     * @return: an integer
     */
    public int search(int[] a, int target) {
    
        // write your code here
        // 1、如果数组为空或者长度为0 返回-1
        if (a == null || a.length == 0) {
            return -1;
        }
        // 定义两个左右指针
        int left = 0;
        int right = a.length - 1;
        while (left <= right) {
            // 计算中间位置
            int middle = (left + right) / 2;
            // 如果相等那么直接返回
            if (a[middle] == target) {
                return middle;
            }
            // 因为不是绝对的顺序，所以这里看下是往左边继续二分查找还是右边
            // 怎么判断 先不管target情况，看middle 和 left或者right
            // middle >= left 说明左边是升序的 否则右边是升序的
            if (a[middle] >= a[left]) {
                // 左边升序的情况下，target在顺序内就在左边找，否则就去右边找
                if (a[left] <= target && target < a[middle]) {
                    right = middle - 1;
                } else {
                    left = middle + 1; 
                }
            } else {
　　　　　　　　　// 右边顺序的情况下，target在顺序内就在右边找，否则就去左边找
               if (a[middle] <= target && target <= a[right]) {
                    left = middle + 1;
                } else {
                    right = middle - 1;
                }            
            }
        }
       
        return -1;
    }
}