折半查找部分有序

部分有序本周qq群有人咨询SearchinRotatedSortedArray来源：http...

部分有序  本周qq群有人咨询

Search in Rotated Sorted Array

来源：
https://leetcode.com/problems/search-in-rotated-sorted-array/

难度：Difficulty: Hard

题目

Suppose a sorted array is rotated(旋转的) at some pivot unknown to you beforehand(提前的)

eg： 0 1 2 3 4 5 6 7

旋转3个might become

4 5 6 7 0 1 2 3.

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.

分析：

观察：

• 举例就用0-9来打比方很容易观察规律
• 7为旋转点两边都是升序【4 5 6】 【0 1 2 3 】这个问题来了不清楚应该去那边去寻找方向了例如寻找3可能在left 也有可能在right 从7 来看一个升序 一个降序 都可能……..…….从这个思路无法判断，你明确表示出来判断不了，你感觉没问题就是分析不出来呀然后果断在换个思路 这个我一般不具备 不能在这里死磕不然陷入了题目给造成的陷阱去了

Q1 有序数组折半是中间位置和查找元素
现在中间位置可以判断出来
查找元素元素方向无法判断如果不匹配是
去left 还是right寻找

我感觉还是判断趋势
假如array[begin end]
case 1 0 1 2 3 4 5 6 7
特点：7>0
array[end] > array[begin]升序

case 2 4 5 6 7 0 1 2 3
特点：array[end] < array[begin]
旋转点在中间

是升序 还是降序还是
还是混合都有
我用的根据相 邻2个元素 6 7 0
判断出来了还是解决无法判断呢

[quote]Q2一个数组
确定中间位置去判断(相邻元素)
假如是7 left是 升序[4 5 6 7]
你如何判断查找元素3位置
回到问题Q1了
你忘记是有序了
一眼看出3不再这里面呀 3

    关注 架构说