FilesExpand file tree

 master

/

JumpSearch.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

48 lines (40 loc) · 1.39 KB

 master

/

JumpSearch.java

Copy path

Top

File metadata and controls

• Code
• Blame

48 lines (40 loc) · 1.39 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

/**

* JumpSearch: search from an sorted array by jumping ahead fixed number of steps every time.

*

* Time complexity:

* - O(√n). Between Linear Search O(n) and Binary Search O(Logn).

* - Wosrt case: (n/m) + m-1, where n is number of elements, m is number of steps every time.

* Space complexity: O(1).

*

* Start from the leftmost element of the array, and jump m number of elements

* every time then compare x with current element.

* - If found, return the index;

* - Else if current is less than x, keep jumping;

* - Else if current is larger than x, do linear search between last element and current one;

* - Otherwise, not found, return -1.

*

*/

public class JumpSearch {

public static int search(int[] arr, int x) {

int n = arr.length;

int step = (int)Math.floor(Math.sqrt(n));

int last = 0;

int now = step;

while (arr[Math.min(now, n)-1] < x) {

last = now;

now += step;

if (last >= n) return -1;

}

while (arr[last] < x) {

last++;

if (last == Math.min(now, n)) return -1;

}

if (arr[last] == x) return last;

return -1;

}

public static void main(String[] args) {

int[] arr = {3, 5, 7, 10, 15, 20};

System.out.println(JumpSearch.search(arr, 10));

System.out.println(JumpSearch.search(arr, 1));

}

}