【Search In Rotated Sorted Array】cpp
2024-09-02 04:15:43
题目：
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.
代码：
class Solution {
public:
int search(int A[], int n, int target) {
int begin = ;
int end = n-;
while (begin != end)
{
if( begin+ == end )
{
if (A[begin]==target) return begin;
if (A[end]==target) return end;
return -;
}
const int mid = (end+begin)/;
if (A[mid]==target) return mid;
if(target<A[mid])
{
if(A[begin]<A[mid])
{
if(target>=A[begin])
{
end = mid-;
}
else
{
begin = mid+;
}
}
else
{
end = mid-;
}
}
else
{
if(A[begin]<A[mid])
{
begin = mid+;
}
else
{
if(target<=A[end])
{
begin = mid+;
}
else
{
end = mid-;
}
}
}
}
if (A[begin]==target) return begin;
return -;
}
};
Tips:
1. 分target与A[mid]大小情况先讨论
2. 由于前半截或后半截至少一个是有序的，再按照这个来分条件讨论
if else代码中有一些逻辑可以合并，但是考虑到保留原始逻辑更容易被理解，就保留现状了
===================================
第二次过这道题，还是费了一些周折，主要是在于begin+1==end和begin==end这样case的处理。刷了几次，修改了一些细节，AC了。
class Solution {
public:
int search(vector<int>& nums, int target) {
int begin=, end=nums.size()-;
while ( begin<end )
{
if ( begin+==end )
{
if ( nums[begin]==target ) return begin;
if ( nums[end]==target ) return end;
return -;
}
int mid = (begin+end)/;
if ( nums[mid]==target ) return mid;
// first half sorted
if ( nums[begin]<nums[mid] )
{
if ( target>nums[mid] )
{
begin = mid+;
}
else
{
if ( target>=nums[begin] )
{
end = mid-;
}
else
{
begin = mid+;
}
}
continue;
}
// second half sorted
if ( nums[mid]<nums[end] )
{
if ( target<nums[mid])
{
end = mid-;
}
else
{
if ( target<=nums[end])
{
begin = mid+;
}
else
{
end = mid-;
}
}
}
}
return nums[begin]==target?begin:-;
}
};
============================
学习了一种边界条件更简洁的写法，这里能简洁主要是因为把begin+1==end和begin==end的情况都融进了 nums[begin]<=nums[mid]的条件；多了一个等号，就把这些case都给融进去了，提高了代码的效率。
class Solution {
public:
int search(vector<int>& nums, int target) {
int begin=, end=nums.size()-;
while ( begin<=end )
{
int mid = (begin+end)/;
if ( nums[mid]==target ) return mid;
// first half sorted
if ( nums[begin]<=nums[mid] )
{
if ( target>nums[mid] )
{
begin = mid+;
}
else
{
if ( target>=nums[begin] )
{
end = mid-;
}
else
{
begin = mid+;
}
}
continue;
}
// second half sorted
if ( nums[mid]<nums[end] )
{
if ( target<nums[mid])
{
end = mid-;
}
else
{
if ( target<=nums[end])
{
begin = mid+;
}
else
{
end = mid-;
}
}
}
}
return -;
}
};
最新文章
- python学习笔记-（十二）scoket编程基础
- 获取手机通讯录－－ios
- HTC Vive 体验的折腾经历
- 【BZOJ1006】【HNOI2008】神奇的国度（弦图染色）
- 图像显示与加载——opencv（转）
- java基础知识回顾之---java String final类普通方法的应用之“子串在整串中出现的次数”
- uboot---linux
- JS的Dom树小结
- 创建文件DSN
- 十年磨一剑 Delphi重新崛起再写传奇
- Python开发【第十六篇】：AJAX全套（转）
- Win7 Win8 Win10取不到机器码的处理办法
- oracle小记：dba_data_files
- 写出良好风格的JS、CSS代码
- luogu P4403 [BJWC2008]秦腾与教学评估
- 开始写博客，学习Linq（3）
- sqlserver实现分页的几种方式
- BZOJ1053：反素数（数学）
- HTML5 本地存储+layer弹层组件制作记事本
- Alpha阶段事后诸葛亮会议记录