在转动过的有序数组中寻找目标值

http://www.nowcoder.com/questionTerminal/7cd13986c79d4d3a8d928d490db5d707

对旋转数组进行均等划分后，总有一边是有序的，如：

10 11 12 13 14 15 1 2 3
10 11 15 1 2 3 4 5 6 7 8

我们定位到有序的一边后，对比target与有序子数组的左右边界，就可以作出搜索左侧还是右侧的决策。

代码如下：

第16行必须是<=，不能是<，举例——从[3,1]中查找1

//
// Created by jt on 2020/9/3.
//
class Solution {
public:
    /**
     *
     * @param A int整型一维数组
     * @param n int A数组长度
     * @param target int整型
     * @return int整型
     */
    int search(int* A, int n, int target) {
        // write code here
        int left = 0, right = n - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (A[mid] == target) return mid;
            if (A[mid] >= A[left]) {
                // 左侧有序(含A[mid])
                if (A[mid] > target && A[left] <= target)
                    right = mid - 1;
                else
                    left = mid + 1;
            } else {
                // 右侧有序(含A[mid])
                if (A[mid] < target && A[right] >= target)
                    left = mid + 1;
                else
                    right = mid - 1;
            }
        }
        return -1;
    }
};

刷遍天下无敌手文章被收录于专栏

秋招刷题历程

全部评论

推荐最新楼层

Insanity_

C++

问一个问题，如果他的有序不是升序而是降序呢？

送花回复

发布于 2020-11-21 22:02

ypqhappy

C++

做过几个类似的题目感觉题目默认就是升序（只针对做题来说的话）

送花回复

发布于 2021-04-07 17:02

秋招专场

校招火热招聘中

官网直投

Insanity_

C++

int a[] = {1,5,4,3,2}时，查找5这个数字，代码将会有错误的输出

送花回复

发布于 2020-11-21 22:12

守夜人zzx

C++

算法有漏洞； A[mid] > target && A[left] <= target不能判断是升序， A[mid] < target && A[right] >= target也不能判断是降序；你可以试试输入：[2,1,9,8,7,6,5,4,3],6

送花回复

发布于 2020-12-01 17:11

KKK李

拼多多_基础电商_后端研发工程师

这个答案是有问题的啊，早点删了吧

送花回复

发布于 2021-02-07 10:53

牛客776301637号

Java

public class Solution { public static void main(String[] args) { System.out.println(new Solution().search(new int[]{1}, 0)); System.out.println(new Solution().search(new int[]{3, 2, 1}, 1)); System.out.println(new Solution().search(new int[]{258, 260, 265, 266, 268, 269, 271, 275, 276, 278, 280, 282, 287, 288, 289, 293, 2, 4, 5, 9, 16, 23, 24, 25, 26, 27, 28, 36, 37, 46, 47, 52, 55, 56, 60, 63, 67, 71, 74, 75, 76, 79, 80, 81, 82, 92, 97, 99, 103, 104, 106, 109, 111, 112, 117, 121, 125, 131, 133, 136, 141, 142, 143, 144, 154, 160, 161, 168, 169, 179, 187, 190, 201, 202, 204, 206, 208, 209, 211, 213, 218, 220, 222, 224, 225, 226, 229, 230, 231, 234, 240, 241, 242, 243, 244, 245, 247, 249, 252, 253, 254, 257}, 81)); } /** * @param A int整型一维数组 * @param target int整型 * @return int整型 */ public int search(int[] A, int target) { // write code here int start = 0, end = A.length - 1; while (start <= end) { int mid = start + (end - start) / 2; if (A[mid] == target) { return mid; } if(A[start] == target){ return start; } if(A[end] == target){ return end; } if (A[mid] >= A[start]) { if (A[mid] > target && A[start] < target) { end = mid - 1; } else { start = mid + 1; } } else { if (A[mid] < target && A[end] > target) { start = mid + 1; } else { end = mid - 1; } } } return -1; } }

送花回复

发布于 2021-03-10 09:22

慕少晴

算法工程师

我去LeetCode上看了一下，原题条件是升序，牛客网题目太不严谨了

送花回复

发布于 2021-04-19 12:12