【Lintcode】062.Search in Rotated Sorted Array

谁借莪１个温暖的怀抱￠ 2021-10-01 01:14 180阅读 0赞

题目：

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., `0 1 2 4 5 6 7` might become `4 5 6 7 0 1 2`).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

**Example**

For `[4, 5, 1, 2, 3]` and `target=1`, return `2`.

For `[4, 5, 1, 2, 3]` and `target=0`, return `-1`.

题解：

class Solution {
    public:
        /**
         * @param nums: a rotated sorted array
         * @return: the minimum number in the array
         */
        int search(vector<int> &A, int target) {
            if (A.empty()) {
                return -1;
            }
            int start = 0, end = A.size() - 1;
            while (start + 1 < end) {
                int mid = start + (end - start) / 2;
                if (A[mid] == target) {
                    return mid;
                } 
                if (A[start] < A[mid]) {
                    if (A[start] <= target && target <= A[mid]) {
                        end = mid;
                    } else {
                        start = mid;
                    }
                } else {
                    if (A[mid] <= target && target <= A[end]) {
                        start = mid;
                    } else {
                        end = mid;
                    }
                }
            }
            
            if (A[start] == target) {
                return start;
            } else if (A[end] == target){
                return end;
            }
            
            return -1;
        }
    };

转载于:https://www.cnblogs.com/Atanisi/p/6822611.html

发表评论取消回复

表情：

评论列表（有 0 条评论，180人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode - Medium - 33. Search in Rotated Sorted Array

Topic Array Binary Search Description [https://leetcode.com/problems/search

红太狼/ 2023年01月04日 11:53/ 0 赞/ 115 阅读

相关 LeetCode之Search in Rotated Sorted Array二

题目：Follow up for ”Search in Rotated Sorted Array”: What if duplicates are allowed? Wou

古城微笑少年丶/ 2022年08月05日 12:17/ 0 赞/ 105 阅读

相关 LeetCode之Search in Rotated Sorted Array

题目：Suppose a sorted array is rotated at some pivot unknown to you beforehand. (i.e., 0

喜欢ヅ旅行/ 2022年08月05日 12:17/ 0 赞/ 97 阅读

相关 leetcode 33. Search in Rotated Sorted Array 二分查找

Suppose an array sorted in ascending order is rotated at some pivot unknown to you befor

痛定思痛。/ 2022年06月09日 09:42/ 0 赞/ 93 阅读

相关 81. Search in Rotated Sorted Array II

描述： Follow up for “Search in Rotated Sorted Array”: What if duplicates are allowed?

￡神魔★判官ぃ/ 2022年06月02日 01:27/ 0 赞/ 93 阅读

相关 33. Search in Rotated Sorted Array

描述： Suppose an array sorted in ascending order is rotated at some pivot unknown to you

深藏阁楼爱情的钟/ 2022年06月02日 01:26/ 0 赞/ 115 阅读

相关 81. Search in Rotated Sorted Array II

Suppose an array sorted in ascending order is rotated at some pivot unknown to you befor

谁借莪１个温暖的怀抱￠/ 2022年03月07日 14:45/ 0 赞/ 155 阅读

相关 leeetcode33 Search in Rotated Sorted Array

问题描述 1. 假设按照升序排序的数组在预先未知的某个点上进行了旋转。( 例如，数组 \[0,1,2,4,5,6,7\] 可能变为 \[4,5,6,7,0,1,2\]

拼搏现实的明天。/ 2021年12月03日 23:17/ 0 赞/ 125 阅读

相关 leetcode--Search in Rotated Sorted Array II

Follow up for "Search in Rotated Sorted Array": What if duplicates are allowed? Would

Bertha 。/ 2021年10月16日 01:12/ 0 赞/ 184 阅读

相关【Lintcode】062.Search in Rotated Sorted Array

题目： Suppose a sorted array is rotated at some pivot unknown to you beforehand. (i.e.,

谁借莪１个温暖的怀抱￠/ 2021年10月01日 01:14/ 0 赞/ 181 阅读