首页 > 其他 > 详细

LeetCode - Refresh - Search in Rotated Sorted Array

时间:2015-03-23 15:04:01      阅读:109      评论:0      收藏:0      [点我收藏+]

Two condition need to equal:

1. A[mid] >= A[start]. Because mid = (start + end)/2; it shifts left

2. A[end] >= target. Since did not check A[end] now.

 1 class Solution {
 2 public:
 3     int search(int A[], int n, int target) {
 4         int start = 0, end = n-1, mid = 0;
 5         while (start <= end) {
 6             mid = (start + end)/2;
 7             if (A[mid] == target) return mid;
 8             if (A[mid] >= A[start]) {
 9                 if (A[start] > target) {
10                     start = mid+1;
11                 } else if (A[mid] > target) {
12                     end = mid - 1;
13                 } else start = mid+1;
14             } else {
15                 if (A[mid] > target) end = mid-1;
16                 else if (A[end] >= target) start = mid+1;
17                 else end = mid-1;
18             }
19         }
20         return -1;
21     }
22 };

 

LeetCode - Refresh - Search in Rotated Sorted Array

原文:http://www.cnblogs.com/shuashuashua/p/4359517.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!