FilesExpand file tree

 master

/

SearchinRotatedArray.java

Copy path

BlameMore file actions

BlameMore file actions

Latest commit

 

History

History

History

56 lines (51 loc) · 1.47 KB

 master

/

SearchinRotatedArray.java

Top

File metadata and controls

• Code
• Blame

56 lines (51 loc) · 1.47 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

public class SearchinRotatedArray {

public static void main(String[] args) {

int[] nums = {6,7,1,2,3,4,5};

System.out.println(SearchRotatearray(nums,6));

}

public static int SearchRotatearray(int[] nums, int target){

int pivot = pivot(nums);

if(pivot == -1){

return Binaryserach(nums,target,0,nums.length-1);

}

if(nums[pivot]==target){

return pivot;

}

if(target >= nums[0]){

return Binaryserach(nums,target,0,pivot-1);

}

return Binaryserach(nums,target,pivot+1,nums.length-1);

}

public static int Binaryserach(int[] nums, int target, int start,int end){

while(start<=end){

int mid = (start+end)/2;

if(target<nums[mid]){

end = mid-1;

}else if(target>nums[mid]){

start = mid+1;

}else{

return mid;

}

}

return -1;

}

public static int pivot(int[] nums){

int start = 0;

int end = nums.length-1;

while(start<=end){

int mid = (start+end)/2;

if(mid < end && nums[mid]>nums[mid+1]){

return mid;

}

if(mid>start && nums[mid]<nums[mid-1]){

return mid-1;

}

if(nums[mid]<=nums[start]){

end = mid-1;

}else{

start = mid+1;

}

}

return -1;

}

}