FilesExpand file tree

 master

/

BinarySearch.js

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

52 lines (46 loc) · 1.71 KB

 master

/

BinarySearch.js

Copy path

Top

File metadata and controls

• Code
• Blame

52 lines (46 loc) · 1.71 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

/* Binary Search: https://en.wikipedia.org/wiki/Binary_search_algorithm

*

* Search a sorted array by repeatedly dividing the search interval

* in half. Begin with an interval covering the whole array. If the value of the

* search key is less than the item in the middle of the interval, narrow the interval

* to the lower half. Otherwise narrow it to the upper half. Repeatedly check until the

* value is found or the interval is empty.

*/

function binarySearchRecursive (arr, x, low = 0, high = arr.length - 1) {

const mid = Math.floor(low + (high - low) / 2)

if (high >= low) {

if (arr[mid] === x) {

// item found => return its index

return mid

}

if (x < arr[mid]) {

// arr[mid] is an upper bound for x, so if x is in arr => low <= x < mid

return binarySearchRecursive(arr, x, low, mid - 1)

} else {

// arr[mid] is a lower bound for x, so if x is in arr => mid < x <= high

return binarySearchRecursive(arr, x, mid + 1, high)

}

} else {

// if low > high => we have searched the whole array without finding the item

return -1

}

}

function binarySearchIterative (arr, x, low = 0, high = arr.length - 1) {

while (high >= low) {

const mid = Math.floor(low + (high - low) / 2)

if (arr[mid] === x) {

// item found => return its index

return mid

}

if (x < arr[mid]) {

// arr[mid] is an upper bound for x, so if x is in arr => low <= x < mid

high = mid - 1

} else {

// arr[mid] is a lower bound for x, so if x is in arr => mid < x <= high

low = mid + 1

}

}

// if low > high => we have searched the whole array without finding the item

return -1

}

export { binarySearchIterative, binarySearchRecursive }