FilesExpand file tree

 master

/

SearchRange.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

79 lines (56 loc) · 1.96 KB

 master

/

SearchRange.java

Copy path

Top

File metadata and controls

• Code
• Blame

79 lines (56 loc) · 1.96 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

75

76

77

78

79

//34. Search for a Range My Submissions Question

//Total Accepted: 77172 Total Submissions: 267558 Difficulty: Medium

//Given a sorted array of integers, find the starting and ending position of a given target value.

//

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

//

//If the target is not found in the array, return [-1, -1].

//

//For example,

//Given [5, 7, 7, 8, 8, 10] and target value 8,

//return [3, 4].

public class Solution {

int a[]={-1,-1};

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

int len=nums.length;

if(len==0)

return null;

// a[0]=-1;

// a[1]=-1;

int upper,lower;

upper=len-1;

lower=0;

//int pivot=upper/lower;

int x = binary(nums,lower,upper,target);

//System.out.println(x);

return a;

}

public int binary(int[] nums,int lower,int upper,int target)

{

int pivot=(upper-lower)/2 + lower;

// System.out.println("Pivot : " + nums[pivot] );

if(nums[pivot]==target)

{

if(a[0]==-1)

a[0]=pivot;

if(pivot<a[0])

a[0]=pivot;

if(pivot>a[1])

a[1]=pivot;

if(lower>=upper)

return -1;

binary(nums,lower,pivot-1,target);

binary(nums,pivot+1,upper,target);

return 0;

}

if(lower>=upper)

return -1;

if(nums[pivot]>target)

{

// System.out.println("in here");

return binary(nums,lower,pivot-1,target);

}

else

return binary(nums,pivot+1,upper,target);

}

}