forked from version1-workspace/ws-0200-js-practice
-
Notifications
You must be signed in to change notification settings - Fork 0
/
002_search.js
61 lines (54 loc) · 1.4 KB
/
002_search.js
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
/**
* 2.3.1 リニアサーチ
*
* リニアサーチを実装してください。(入力は数値のみ)
* 二つ目の引数に合致した配列の添字を返却してください。
* 合致のする数字のない場合は-1を返却してください。
*
* example:
* [1, 3, 2, 4, 5], 3 => 1
* [5, 3, 2, 1], 6 => -1
*/
function linearSearch(array, target) {
for (let i = 0; i < array.length; i++) {
if (array[i] === target) {
return i;
}
}
return -1;
}
/**
* 2.3.2 バイナリサーチ
*
* バイナリサーチを実装してください。(入力は数値のみ)
*
* example:
* [1, 2, 3, 4, 5], 2 => 2
* [1, 2, 3, 4] 5 => -1
*/
function binarySearch(array, target) {
// 配列の位置を設定
let low = 0; //左端
let high = array.length - 1; //右端
//左端が右端以下の間(1つの要素に絞られるまで)は処理を続ける
while (low <= high) {
mid = low + high; // 真ん中の位置
guess = array[mid]; // 真ん中の要素
//真ん中の要素がtargetと合致したら
if (guess == target) {
//位置を返す
return mid;
//真ん中の要素がtargetより大きかったら
} else if (guess > target) {
//右端の位置は要素の位置-1
high = mid - 1;
} else {
low = mid + 1;
}
}
return -1;
}
module.exports = {
linearSearch,
binarySearch,
};