FilesExpand file tree

 master

/

SearchInRotatedSortedArrayII.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

74 lines (67 loc) · 2.22 KB

 master

/

SearchInRotatedSortedArrayII.java

Copy path

Top

File metadata and controls

• Code
• Blame

74 lines (67 loc) · 2.22 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

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

package com.hncboy;

/**

* @author hncboy

* @date 2019/11/18 13:23

* @description 81.搜索旋转排序数组 II

*

* 假设按照升序排序的数组在预先未知的某个点上进行了旋转。

* ( 例如，数组 [0,0,1,2,2,5,6] 可能变为 [2,5,6,0,0,1,2] )。

* 编写一个函数来判断给定的目标值是否存在于数组中。若存在返回 true，否则返回 false。

*

* 示例 1:

* 输入: nums = [2,5,6,0,0,1,2], target = 0

* 输出: true

*

* 示例 2:

* 输入: nums = [2,5,6,0,0,1,2], target = 3

* 输出: false

*

* 进阶:

* 这是 搜索旋转排序数组 的延伸题目，本题中的 nums  可能包含重复元素。

* 这会影响到程序的时间复杂度吗？会有怎样的影响，为什么？

*/

public class SearchInRotatedSortedArrayII {

public static void main(String[] args) {

SearchInRotatedSortedArrayII s = new SearchInRotatedSortedArrayII();

int[] nums1 = {2, 5, 6, 0, 0, 1, 2};

int[] nums2 = {2, 5, 6, 0, 0, 1, 2};

int[] nums3 = {1, 3};

System.out.println(s.search(nums1, 0));

System.out.println(s.search(nums2, 3));

System.out.println(s.search(nums3, 3));

}

private boolean search(int[] nums, int target) {

int left = 0;

int right = nums.length - 1;

if (right == 0 && nums[0] == target) {

return true;

}

while (left <= right) {

int mid = left + (right - left) / 2;

if (nums[mid] == target) {

return true;

}

if (nums[left] == nums[mid]) {

left++;

continue;

}

// 至少是有一半是有序的

if (nums[left] < nums[mid]) {

// 前半部分有序

if (target >= nums[left] && target < nums[mid]) {

right = mid - 1;

} else {

left = mid + 1;

}

} else {

// 后半部分有序

if (target <= nums[right] && target > nums[mid]) {

left = mid + 1;

} else {

right = mid - 1;

}

}

}

return false;

}

}