binary_search/BinarySearch.kt - master - uizadcz/Algorithm

binary_search/BinarySearch.kt
78 строк2 KB
ursa
BinarySearch
27 сен 2024, 14:41
27 сен 2024, 14:41a6acfd8
/**
 * https://leetcode.com/problems/binary-search/description/
 *
 * Given an array of integers nums which is sorted in ascending order,
 * and an integer target, write a function to search target in nums.
 * If target exists, then return its index. Otherwise, return -1.
 *
 * You must write an algorithm with O(log n) runtime complexity.
 *
 * Example 1:
 *
 * Input: nums = [-1,0,3,5,9,12], target = 9
 * Output: 4
 * Explanation: 9 exists in nums and its index is 4
 *
 * Example 2:
 *
 * Input: nums = [-1,0,3,5,9,12], target = 2
 * Output: -1
 * Explanation: 2 does not exist in nums so return -1
 *
 * Constraints:
 * 1 <= nums.length <= 10(4)
 * -10(4) < nums[i], target < 10(4)
 * All the integers in nums are unique.
 * nums is sorted in ascending order.
 */

class BinarySearchIterative {
    /**
     * Iterative binary search
     * Time complexity - O(log n)
     * Space complexity - O(1)
     */
    fun search(nums: IntArray, target: Int): Int {
        var leftSide = 0
        var rightSide = nums.size - 1

        while (rightSide >= leftSide) {
            var midSide = (leftSide + rightSide) / 2

            when {
                nums[midSide] == target -> midSide
                nums[midSide] > target -> rightSide = midSide - 1
                nums[midSide] < target -> leftSide = midSide + 1
            }
        }

        return -1
    }
}

class BinarySearchRecursive {
    /**
     * Recursive binary search
     * Time complexity - O(log n)
     * Space complexity - O(log n)
     */
    fun search(nums: IntArray, target: Int): Int {
        if (nums.isEmpty()) return -1

        return search(nums, target, 0, nums.lastIndex)
    }

    fun search(nums: IntArray, target: Int, start: Int, end: Int): Int {
        if (start > end) {
            return -1
        }
        val mid = (start + end) / 2
        return if (nums[mid] == target) {
            mid
        } else if (nums[mid] > target) {
            search(nums, target, start, mid - 1)
        } else {
            search(nums, target, mid + 1, end)
        }
    }
}