折半查找部分有序
部分有序本周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
关注 架构说
微信扫一扫关注公众号