-
Notifications
You must be signed in to change notification settings - Fork 0
/
QuickSearchInArray.kt
65 lines (56 loc) · 1.61 KB
/
QuickSearchInArray.kt
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
package binarysearch
import java.io.File
fun main() {
val input = File("input.txt").bufferedReader()
val output = File("output.txt")
output.writeText("")
val n = input.readLine().toInt()
val nums = input.readLine().split(' ').map { it.toInt() }.sorted()
val k = input.readLine().toInt()
val res = StringBuilder()
repeat(k) {
val (left, right) = input.readLine().split(' ').map { it.toInt() }
var add = -1
var indexLeft = nums.binarySearch(left)
if (indexLeft < 0) {
indexLeft = -indexLeft - 1
add = 0
} else {
indexLeft = firstBinSearch(0, indexLeft, nums, left) - 1
}
var indexRight = nums.binarySearch(right)
if (indexRight < 0) {
indexRight = -indexRight - 1
} else {
indexRight = lastBinSearch(indexRight, nums.lastIndex, nums, right) + 1
}
res.append("${indexRight - indexLeft + add} ")
}
output.appendText(res.toString())
}
fun lastBinSearch(left: Int, right: Int, nums: List<Int>, searched: Int): Int {
var l = left
var r = right
while (l < r) {
val medium = (l + r + 1) / 2
if (nums[medium] == searched) {
l = medium
} else {
r = medium - 1
}
}
return l
}
fun firstBinSearch(left: Int, right: Int, nums: List<Int>, searched: Int): Int {
var l = left
var r = right
while (l < r) {
val medium = (l + r) / 2
if (nums[medium] == searched) {
r = medium
} else {
l = medium + 1
}
}
return l
}