FilesExpand file tree

 master

/

SearchInRotatedSortedArray.java

Copy path

BlameMore file actions

BlameMore file actions

Latest commit

 

History

History

History

52 lines (51 loc) · 1.62 KB

 master

/

SearchInRotatedSortedArray.java

Top

File metadata and controls

• Code
• Blame

52 lines (51 loc) · 1.62 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

package com.yangchd.leetcode.medium;

/**

* @author yangchd 2018/7/3.

*

* 33. Search in Rotated Sorted Array

* Suppose an array sorted in ascending order 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.

* Your algorithm's runtime complexity must be in the order of O(log n).

*

* Example 1:

* Input: nums = [4,5,6,7,0,1,2], target = 0

* Output: 4

*

* Example 2:

* Input: nums = [4,5,6,7,0,1,2], target = 3

* Output: -1

*

*/

public class SearchInRotatedSortedArray {

class Solution {

public int search(int[] nums, int target) {

if (nums.length <= 0) {

return -1;

}

int low = 0;

int high = nums.length - 1;

while (low <= high) {

int middle = low + (high - low) / 2;

if (nums[middle] == target) {

return middle;

}

if (nums[low] > nums[middle]) {

if (nums[middle] < target && target <= nums[high]) {

low = middle + 1;

} else {

high = middle - 1;

}

} else {

if (target < nums[middle] && target >= nums[low]) {

high = middle - 1;

} else {

low = middle + 1;

}

}

}

return -1;

}

}

}