LintCode 搜索旋转排序数组题目分析代码

题目

假设有一个排序的按未知的旋转轴旋转的数组(比如,0 1 2 4 5 6 7 可能成为4 5 6 7 0 1 2)。给定一个目标值进行搜索,如果在数组中找到目标值返回数组中的索引位置,否则返回-1。

你可以假设数组中不存在重复的元素。

样例 给出[4, 5, 1, 2, 3]和target=1,返回 2

给出[4, 5, 1, 2, 3]和target=0,返回 -1

分析

代码

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
        if (A == null || A.length == 0) {
            return -1;
        }

        int start = 0;
        int end = A.length - 1;
        int mid;
        
        while (start + 1 < end) {
            mid = start + (end - start) / 2;
            if (A[mid] == target) {
                return mid;
            }
            if (A[start] < A[mid]) {
                // situation 1, red line
                if (A[start] <= target && target <= A[mid]) {
                    end = mid;
                } else {
                    start = mid;
                }
            } else {
                // situation 2, green line
                if (A[mid] <= target && target <= A[end]) {
                    start = mid;
                } else {
                    end = mid;
                }
            }
        } // while
        
        if (A[start] == target) {
            return start;
        }
        if (A[end] == target) {
            return end;
        }
        return -1;
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏我是业余自学C/C++的

矩阵

1395
来自专栏开源优测

[快学Python3]Number(数字)

概述 Python数值数据类型用于存储数值,并有一系列对应的函数用于处理数值类型的数据。 在Python中支持三种不同类型的数值类型: 整型(int) 通常称为...

2599
来自专栏前端儿

最长公共子序列

咱们就不拐弯抹角了,如题,需要你做的就是写一个程序,得出最长公共子序列。 tip:最长公共子序列也称作最长公共子串(不要求连续),英文缩写为LCS(Longes...

1141
来自专栏bboysoul

1493: C语言实验题――圆柱体计算

描述:已知圆柱体的底面半径r和高h,计算圆柱体底面周长和面积、圆柱体侧面积以及圆柱体体积。 输入:输入数据有一行,包括2个正实数r和h,以空格分隔。 输出:...

791
来自专栏Python中文社区

NumPy二元运算的broadcasting机制

NumPy中有一个非常方便的特性:broadcasting。当我们对两个不同长度的numpy数组作二元计算(如相加,相乘)的时候,broadcasting就在背...

3538
来自专栏用户2442861的专栏

桶排序

http://blog.csdn.net/houapple/article/details/6480100

2074
来自专栏软件开发 -- 分享 互助 成长

二维数组简介与使用

前言 本文将探讨一下关于二维数组在内存中的存储和二维数组在参数传递时的使用。 一、二维数组在内存中的存储 如果定义一个这样的二维数组int a[3][4]={{...

23410
来自专栏tkokof 的技术,小趣及杂念

编程小知识之 Random接口返回值

平日工作中,(伪)随机数的使用一定是避不开的,拿 C# 为例,System 命名空间下的 Random 类型一般都是我们生成(伪)随机数的第一选择:

963
来自专栏chenjx85的技术专栏

leetcode-33-搜索旋转排序数组

( 例如,数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。

1033
来自专栏数据结构与算法

P3391 【模板】文艺平衡树(Splay)

题目背景 这是一道经典的Splay模板题——文艺平衡树。 题目描述 您需要写一种数据结构(可参考题目标题),来维护一个有序数列,其中需要提供以下操作:翻转一个区...

4137

扫码关注云+社区

领取腾讯云代金券