forked from aishraj/JavaScript-Interview-Questions
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy path004.js
More file actions
72 lines (57 loc) · 1.7 KB
/
Copy path004.js
File metadata and controls
72 lines (57 loc) · 1.7 KB
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
/*
* <!--
* This program is distributed under
* the terms of the MIT license.
* Please see the LICENSE file for details.
* -->
*/
/*
* Implement a function to perform binary search on a sorted array of integers
* to return the index of a given target integer.
* Use the following method prototype:
*
* function binarySearch(array, lower, upper, target);
*/
/*____________________________________________________________________________*/
/**
* @function {public static} binarySearch
*
* Performs a binary search on a sorted `Array`.
*
* @param {Array} array - the `Array` to search.
* @param {Integer} lower - the lower index to search.
* @param {Integer} upper - the upper index to search.
* @param {Integer} target - the element to match.
*
* @return the matched elements index.
*
* @throw exception if element is not found, or array is not ordered,
* or indexes are not in order.
*/
function binarySearch(array, lower, upper, target) {
var range = upper - lower;
if (range < 0) {
throw 'Limits are reversed.';
}
if (range === 0 && array[lower] !== target) {
throw 'Target not in array.';
}
if (array[lower] > array[upper]) {
throw 'Array unordered.';
}
var center = Math.floor(range/2) + lower;
if (target === array[center]) {
return center;
}
if (target < array[center]) {
return binarySearch(array, lower, center-1, target);
}
return binarySearch(array, center+1, upper, target);
}
/*____________________________________________________________________________*/
var ar = [1, 10, 31, 52, 122, 291, 422, 1096];
console.log(binarySearch(ar, 0, 7, 291));
/*
Output: ($ /usr/bin/node 004.js)
5
*/