AI Mobile CodersJoin community
← DSA practice

Binary Search on a Sorted Array

EasyBinary searchO(log n) time · O(1) space

The problem

Given a sorted array and a target, return the target's index or -1 if it is absent.

[-1, 0, 3, 5, 9, 12], target = 9   →  4
[-1, 0, 3, 5, 9, 12], target = 2   →  -1
Stuck? Open one hint

Where does the midpoint calculation overflow, and should the loop condition be < or <= ?

Show the worked solution

Halve the search space each step: compare the middle element with the target and discard the half that cannot contain it.

The two places people lose the point:

  • Midpoint overflow — use low + (high - low) / 2, not (low + high) / 2.
  • Loop bounds — with an inclusive high, the condition must be low <= high, otherwise a single-element range is never checked.

Expect the follow-up: find the first occurrence, or the insert position. Both are the same loop with the "found" case continuing to search left.

KotlinO(log n) time · O(1) space
fun search(nums: IntArray, target: Int): Int {
    var low = 0
    var high = nums.size - 1
    while (low <= high) {
        val mid = low + (high - low) / 2
        when {
            nums[mid] == target -> return mid
            nums[mid] < target -> low = mid + 1
            else -> high = mid - 1
        }
    }
    return -1
}