LeetCode Entry

704. Binary Search

01.04.2023 easy 2023 kotlin

For more robust code

704. Binary Search easy

blog post


fun search(nums: IntArray, target: Int): Int {
    var lo = 0
    var hi = nums.lastIndex
    while (lo <= hi) {
        val mid = lo + (hi - lo) / 2
        if (nums[mid] == target) return mid
        if (nums[mid] < target) lo = mid + 1
        else hi = mid - 1
    }
    return -1
}

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/167

Intuition

Just write binary search.

Approach

For more robust code:

  • use including ranges lo..hi
  • check the last condition lo == hi
  • always check the exit condition == target
  • compute mid without the integer overflow
  • always move the boundary mid + or mid - 1
  • check yourself where to move the boundary, imagine moving closer to the target

    Complexity

  • Time complexity: \(O(log_2(n))\)
  • Space complexity: \(O(1)\)