Commit 26a5191

committed

implemented binary search

1 parent 87a4693 commit 26a5191Copy full SHA for 26a5191

File tree

+37

-0

lines changed

+37

-0

lines changed

Lines changed: 22 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,22 @@`
	`1`	`+// A recursive binary search function. It returns true if target`
	`2`	`+// is present in given array, otherwise return false`
	`3`	`+const binarySearch = (arr, lo, hi, target) => {`
	`4`	`+ // element is not present in array`
	`5`	`+ if (lo > hi) return false;`
	`6`	`+`
	`7`	`+ const mid = Math.floor(hi + lo / 2);`
	`8`	`+`
	`9`	`+ // If the element is present at the middle`
	`10`	`+ if (arr[mid] === target) return true;`
	`11`	`+`
	`12`	`+ // If element is smaller than mid, then`
	`13`	`+ // it can only be present in left subarray`
	`14`	`+ if (arr[mid] > target) {`
	`15`	`+ return binarySearch(arr, lo, mid - 1, target);`
	`16`	`+ }`
	`17`	`+`
	`18`	`+ // Else the element can only be present in right subarray`
	`19`	`+ return binarySearch(arr, mid + 1, hi, target);`
	`20`	`+};`
	`21`	`+`
	`22`	`+module.exports = (arr, target) => binarySearch(arr, 0, arr.length - 1, target);`

Lines changed: 15 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,15 @@`
	`1`	`+const binarySearch = require('../../src/search/binary');`
	`2`	`+`
	`3`	`+describe('binary search unit test:', () => {`
	`4`	`+ it('Test#1 fail test', async () => {`
	`5`	`+ const want = false;`
	`6`	`+ const got = binarySearch([2, 3, 5, 6, 7, 9], 13);`
	`7`	`+ expect(got).toBe(want);`
	`8`	`+ });`
	`9`	`+`
	`10`	`+ it('Test#2 find a value', async () => {`
	`11`	`+ const want = true;`
	`12`	`+ const got = binarySearch([-7, -7, -3, 6, 17, 34, 42, 50, 52, 83, 87, 89, 96], 96);`
	`13`	`+ expect(got).toBe(want);`
	`14`	`+ });`
	`15`	`+});`

Comments

(0)