Binary Search is one of the most important algorithms every developer must master. In this guide, we’ll solve 11 essential binary search problems in Kotlin, each with clean solutions, expected outputs, and detailed explanations.
1. Binary Search (Standard)
Copy
fun binarySearch(arr: IntArray, target: Int): Int {
var left = 0
var right = arr.size - 1
while (left <= right) {
val mid = left + (right - left) / 2
when {
arr[mid] == target -> return mid
arr[mid] < target -> left = mid + 1
else -> right = mid - 1
}
}
return -1
}
fun main() {
val arr = intArrayOf(1, 3, 5, 7, 9)
println(binarySearch(arr, 5)) // Expected 2
}
Output:2
Explanation: Element 5 is found at index 2.
2. First Bad Version
Copy
// Assume isBadVersion is defined externally
fun firstBadVersion(n: Int): Int {
var left = 1
var right = n
var ans = n
while (left <= right) {
val mid = left + (right - left) / 2
if (isBadVersion(mid)) {
ans = mid
right = mid - 1
} else left = mid + 1
}
return ans
}
Explanation: Finds the earliest bad version using binary search to minimize API calls.
3. Search Insert Position
Copy
fun searchInsert(nums: IntArray, target: Int): Int {
var left = 0
var right = nums.size - 1
while (left <= right) {
val mid = left + (right - left) / 2
when {
nums[mid] == target -> return mid
nums[mid] < target -> left = mid + 1
else -> right = mid - 1
}
}
return left
}
fun main() {
val nums = intArrayOf(1, 3, 5, 6)
println(searchInsert(nums, 5)) // 2
println(searchInsert(nums, 2)) // 1
}
Output:2
1
Explanation: Returns index if found; otherwise, returns the insertion index.
4. Guess Number Higher or Lower
Copy
// Assume guess(num) API is provided
fun guessNumber(n: Int): Int {
var left = 1
var right = n
while (left <= right) {
val mid = left + (right - left) / 2
when (guess(mid)) {
0 -> return mid
-1 -> right = mid - 1
1 -> left = mid + 1
}
}
return -1
}
Explanation: Uses binary search to find the hidden number with minimal guesses.
5. Peak Index in Mountain Array
Copy
fun peakIndexInMountainArray(arr: IntArray): Int {
var left = 0
var right = arr.size - 1
while (left < right) {
val mid = left + (right - left) / 2
if (arr[mid] < arr[mid + 1]) left = mid + 1
else right = mid
}
return left
}
fun main() {
val arr = intArrayOf(0, 2, 4, 3, 1)
println(peakIndexInMountainArray(arr)) // 2
}
Output:2
Explanation: The peak element 4 is at index 2.
6. Find Smallest Letter Greater Than Target
Copy
fun nextGreatestLetter(letters: CharArray, target: Char): Char {
var left = 0
var right = letters.size - 1
var ans = letters[0]
while (left <= right) {
val mid = left + (right - left) / 2
if (letters[mid] > target) {
ans = letters[mid]
right = mid - 1
} else left = mid + 1
}
return ans
}
fun main() {
val letters = charArrayOf('c','f','j')
println(nextGreatestLetter(letters, 'd')) // f
}
Output:f
Explanation: Finds the smallest letter greater than d, which is f.
7. Two Sum (Sorted)
Copy
fun twoSum(numbers: IntArray, target: Int): IntArray {
var left = 0
var right = numbers.size - 1
while (left < right) {
val sum = numbers[left] + numbers[right]
when {
sum == target -> return intArrayOf(left + 1, right + 1)
sum < target -> left++
else -> right--
}
}
return intArrayOf(-1, -1)
}
fun main() {
val numbers = intArrayOf(2, 7, 11, 15)
println(twoSum(numbers, 9).contentToString()) // [1, 2]
}
Output:[1, 2]
Explanation: 2 + 7 = 9, found at indices [1, 2] (1-based).
8. Two Sum Less Than K
Copy
fun twoSumLessThanK(nums: IntArray, k: Int): Int {
nums.sort()
var left = 0
var right = nums.size - 1
var maxSum = -1
while (left < right) {
val sum = nums[left] + nums[right]
if (sum < k) {
maxSum = maxOf(maxSum, sum)
left++
} else right--
}
return maxSum
}
fun main() {
val nums = intArrayOf(34,23,1,24,75,33,54,8)
println(twoSumLessThanK(nums, 60)) // 58
}
Output:58
Explanation: The maximum sum less than 60 is 58 (34 + 24).
9. Count Negative Numbers in a Sorted Matrix
Copy
fun countNegatives(grid: Array): Int {
var count = 0
var row = 0
var col = grid[0].size - 1
while (row < grid.size && col >= 0) {
if (grid[row][col] < 0) {
count += (grid.size - row)
col--
} else row++
}
return count
}
fun main() {
val grid = arrayOf(
intArrayOf(4,3,2,-1),
intArrayOf(3,2,1,-1),
intArrayOf(1,1,-1,-2),
intArrayOf(-1,-1,-2,-3)
)
println(countNegatives(grid)) // 8
}
Output:8
Explanation: There are 8 negative numbers in the matrix.
10. Valid Perfect Square
Copy
fun isPerfectSquare(num: Int): Boolean {
if (num < 2) return true
var left = 2L
var right = num.toLong() / 2
while (left <= right) {
val mid = left + (right - left) / 2
val square = mid * mid
when {
square == num.toLong() -> return true
square < num -> left = mid + 1
else -> right = mid - 1
}
}
return false
}
fun main() {
println(isPerfectSquare(16)) // true
println(isPerfectSquare(14)) // false
}
Output:true
false
Explanation: 16 is a perfect square (4×4), but 14 is not.
11. Kth Missing Positive Number
Copy
fun findKthPositive(arr: IntArray, k: Int): Int {
var left = 0
var right = arr.size - 1
while (left <= right) {
val mid = left + (right - left) / 2
val missing = arr[mid] - (mid + 1)
if (missing < k) left = mid + 1
else right = mid - 1
}
return left + k
}
fun main() {
val arr = intArrayOf(2,3,4,7,11)
println(findKthPositive(arr, 5)) // 9
}
Output:9
Explanation: The 5th missing number is 9.