leetcode 二分查找 Search in Rotated Sorted Array
LeetCode in 查找 Array 二分 search sorted rotated
2023-09-11 14:15:00 时间
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.
题意:一个已经排序好的数组,被按某个位置旋转了一次。给定一个值target,在该旋转后的数组里查找该值。
思路:二分查找难点在于确定往数组的哪一半段继续二分查找
设起点、中间点、终点分别为 start、middle、end (採用前闭后开的区间表示方法
假设target = A[middle] return middle
假设A[middle] >= A[start],则[start,middle)单调递增
1.假设target < A[middle] && target >= A[start],则 end = middle
2.start = middle + 1, otherwise
假设A[middle] < A[start]。则[middle,end)单调递增
1.假设target > A[middle] && target <= A[end - 1],则 start = middle + 1
2.end = middle, otherwise
复杂度:时间O(log n)。空间O(1)
int search(int A[], int n, int target){ int start = 0, end = n, middle ; while(start < end){ middle = (start + end) / 2; if(A[middle] == target) return middle; if(A[middle] >= A[start]){ if(target >= A[start] && target < A[middle]){ end = middle; }else{ start = middle + 1; } }else{ if(target > A[middle] && target <= A[end - 1]){ start = middle + 1; }else{ end = middle; } } } return -1; }
相关文章
- Java实现 LeetCode 766 托普利茨矩阵(暴力)
- Java实现 LeetCode 671 二叉树中第二小的节点(遍历树)
- Java实现 LeetCode 633 平方数之和(暴力大法)
- Java实现 LeetCode 405 数字转换为十六进制数
- Java实现 LeetCode 229 求众数 II(二)
- Java实现 LeetCode 169 多数元素
- (LeetCode 153)Find Minimum in Rotated Sorted Array
- 【刷题】【LeetCode】000-十大经典排序算法
- [LeetCode] Reverse Words in a String
- LeetCode-728. 自除数
- 【LeetCode 16】最接近的三数之和
- leetcode算法第8题
- Sqlachemy的警告SAWarning: The IN-predicate on "sns_object.BIZ_ID" was invoked with an empty sequence. This results in a contradiction, which nonetheless can be expensive to evaluate.
- Leetcode 剑指 Offer 57. 和为s的两个数字(map查找速率快)
- [LeetCode] 19. 删除链表的倒数第N个节点 ☆☆☆
- [LeetCode] 24. Swap Nodes in Pairs ☆☆☆(链表,相邻两节点交换)
- leetcode之Find All Numbers Disappeared in an Array
- LeetCode:Populating Next Right Pointers in Each Node
- LeetCode 154 Find Minimum in Rotated Sorted Array II
- [LeetCode]Swap Nodes in Pairs 成对交换
- Leetcode--Reverse Nodes in k-Group
- LeetCode Populating Next Right Pointers in Each Node
- [LeetCode] Delete Node in a Linked List
- LeetCode:Find Minimum in Rotated Sorted Array
- leetcode 720. Longest Word in Dictionary
- leetcode 371. Sum of Two Integers
- leetcode 448. Find All Numbers Disappeared in an Array
- 【Leetcode刷题Python】LeetCode 478. 在圆内随机生成点
- 【LeetCode】148. 排序链表