LeetCode Binary Search

发表于 更新于 Disqus： 本文字数： 6.9k 阅读时长 ≈ 6 分钟 
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    func search(_ nums: [Int], _ target: Int) -> Int {
        var i = 0, j = nums.count-1
        while i <= j {
            let mid = i + (j-i)/2
            if nums[mid] == target { return mid }
            else if nums[mid] < target { i = mid+1
            } else { j = mid-1 }
        }
        return -1
    }
}

Sqrt(x)

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    func mySqrt(_ x: Int) -> Int {
        let target = Int(sqrt(Double(x)))
        var i = 0, j = x
        while i <= j {
            let mid = i + (j-i)>>1
            if mid == target { return mid }
            mid < target ? (i=mid+1) : (j=mid-1)
        }
        return i
    }
}

Guess Number Higher or Lower

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution : GuessGame {
    func guessNumber(_ n: Int) -> Int {
        var i = 1, j = n
        while i <= j {
            let mid = i + (j-i)>>1
            switch guess(mid) {
                case -1:
                    j = mid-1
                case 1:
                    i = mid+1
                case 0:
                    return mid
                default:
                    break
            }
        }
        return i
    }
}

Search in Rotated Sorted Array

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    func search(_ nums: [Int], _ target: Int) -> Int {
        var i = 0, j = nums.count-1
        while i <= j {
            let mid = i + (j - i)/2
            if nums[mid] == target {
                return mid
            } else if nums[mid] >= nums[i] {
                (target >= nums[i] && target < nums[mid]) ? (j = mid-1) : (i = mid+1)
            } else {
                (target <= nums[j] && target > nums[mid]) ? (i = mid+1) : (j = mid-1)
            }
        }
        return  -1
    }
}

First Bad Version

1
2
3
4
5
6
7
8
9
10
class Solution: VersionControl {
    func firstBadVersion(_ n: Int) -> Int {
        var i = 1, j = n
        while i <= j {
            let h = i + (j-i)/2
            isBadVersion(h) ? (j = h-1) : (i = h + 1)
        }
        return i
    }
}

Find Peak Element

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    func findPeakElement(_ nums: [Int]) -> Int {
        var l = 0, r = nums.count-1
        while l < r {
            let mid = l+(r-l)>>1
            nums[mid] > nums[mid+1] ? (r = mid) : (l = mid+1)
        }
        return l
    }
    func findPeakElement(_ nums: [Int]) -> Int {
        func search(_ l: Int, _ r: Int) -> Int {
            if (l == r) { return l }
            let mid = l + (r-l)>>1
            return (nums[mid] > nums[mid+1]) ? search(l, mid) : search(mid+1, r)
        }
        return search(0, nums.count-1)
    }
}

Find Minimum in Rotated Sorted Array

1
2
3
4
5
6
7
8
9
10
class Solution {
    func findMin(_ nums: [Int]) -> Int {
        var l = 0, r = nums.count-1
        while l < r {
            let mid = l+(r-l)>>1
            nums[mid] > nums[r] ? (l = mid+1) : (r = mid)
        }
        return nums[l]
    }
}

Search for a Range

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    func searchRange(_ nums: [Int], _ target: Int) -> [Int] {
        if nums.isEmpty { return [-1, -1] }
        var i = 0, j = nums.count-1
        while i < j {
            let mid = i+(j-i)/2
            if nums[mid] == target {
                i = mid; j = mid
            } else if nums[mid] < target {
                i = mid+1
            } else {
                j = mid-1
            }
        }
        while i-1 >= 0, nums[i-1] == target { i -= 1 }
        while j+1 < nums.count, nums[j+1] == target { j += 1 }
        return nums[i] == target ? [i, j] : [-1, -1]
    }
}

Find K Closest Elements

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    func findClosestElements(_ arr: [Int], _ k: Int, _ x: Int) -> [Int] {
        if arr.isEmpty { return [] }
        var i = 0, j = arr.count, ans = [Int
        while i < j {
            let mid = i+(j-i)/2
            if arr[mid] == x { i = mid }
            arr[mid] < x ? (i = mid+1) : (j = mid-1)
        }
        j = i+k < arr.count ? i+k : arr.count-1
        i = (i-k) >= 0 ? (i-k) : 0
        ans = Array(arr[i...j])
        while ans.count > k {
            abs(x-ans.first!) <= abs(x-ans.last!) ? ans.removeLast() : ans.removeFirst()
        }
        return ans
    }
}

Closest Binary Search Tree Value

1
2
3
4
5
6
7
8
9
10
class Solution {
    func closestValue(_ root: TreeNode?, _ target: Double) -> Int {
        var p = root, v = p!.val
        while p != nil {
            if abs(Double(p!.val)-target) < abs(Double(v)-target) { v = p!.val }
            p = target < Double(p!.val) ? p!.left : p!.right
        }
        return v
    }
}

Search in a Sorted Array of Unknown Size

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    func search(_ reader: ArrayReader, _ target: Int) -> Int {
        if reader.get(0) == target { return 0 }
        var i = 0, j = 1
        while reader.get(j) < target {
            i = j; j <<= 1
        }
        while i <= j {
            let mid = i+(j-i)>>1, v = reader.get(mid)
            if v == target { return mid }
            v < target ? (i=mid+1) : (j=mid-1)
        }
        return -1
    }
}

Pow(x, n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    func myPow(_ x: Double, _ n: Int) -> Double {
        var dict = [0: 1.0, 1: x]
        func fastPow(_ x: Double, _ n: Int) -> Double {
            if let v = dict[n] { return v }

            let h = fastPow(x, n/2), v = n&1 == 0 ? h*h : x*h*h
            dict[n] = v
            return v
        }

        let v = fastPow(x, abs(n))
        return n < 0 ? 1/v : v
    }
}

Valid Perfect Square

1
2
3
4
5
6
7
8
9
class Solution {
    func isPerfectSquare(_ num: Int) -> Bool {
        var x = (num+1)/2
        while x*x > num {
            x = (x + num/x) / 2
        }
        return x*x == num
    }
}

Find Smallest Letter Greater Than Target

1
2
3
4
5
6
7
8
class Solution {
    func nextGreatestLetter(_ letters: [Character], _ target: Character) -> Character {
        for c in letters {
            if c > target { return c }
        }
        return letters.first!
    }
}

Find Minimum in Rotated Sorted Array

1
2
3
4
5
6
7
8
9
10
class Solution {
    func findMin(_ nums: [Int]) -> Int {
        var l = 0, r = nums.count-1
        while l < r {
            let mid = l+(r-l)/2
            nums[mid] >= nums[r] ? (l = mid+1) : (r = mid)
        }
        return nums[l]
    }
}

Find Minimum in Rotated Sorted Array II

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    func findMin(_ nums: [Int]) -> Int {
        var l = 0, r = nums.count-1
        while l < r {
            let mid = l+(r-l)/2
            if nums[mid] > nums[r] { l = mid+1 }
            else if nums[mid] < nums[r]  { r = mid }
            else { r -= 1 }
        }
        return nums[l]
    }
}

Intersection of Two Arrays

1
2
3
4
5
6
class Solution {
    func intersection(_ nums1: [Int], _ nums2: [Int]) -> [Int] {
        let set1 = Set(nums1), set2 = Set(nums2)
        return Array(set1.intersection(set2))
    }
}

Intersection of Two Arrays II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    func intersect(_ nums1: [Int], _ nums2: [Int]) -> [Int] {
        var dict = [Int: Int
        for n in nums1 {
            dict[n, default: 0] += 1
        }
        for n in nums2 {
            if let v = dict[n], v > 0 {
                ans.append(n)
                dict[n] = v - 1
            }
        }
        return ans
    }
}

Two Sum II - Input array is sorted

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    func twoSum(_ numbers: [Int], _ target: Int) -> [Int] {
        var i = 0, j = numbers.count-1
        while i < j {
            let v =  numbers[i]+numbers[j]
            if v == target { break }
            v < target ? (i+=1) : (j-=1)
        }
        return [i+1, j+1]
    }
}

Find the Duplicate Number

1
2
3
4
5
6
7
8
9
10
class Solution {
    func findDuplicate(_ nums: [Int]) -> Int {
        var set = Set<Int>(), i = 0
        while i < nums.count {
            if set.contains(nums[i]) { break }
            set.insert(nums[i]); i+=1
        }
        return nums[i]
    }
}

Median of Two Sorted Arrays

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    func findMedianSortedArrays(_ nums1: [Int], _ nums2: [Int]) -> Double {
        var nums = nums1+nums2
        var i = 0, j = 0, k = 0
        while i < nums1.count, j < nums2.count {
            nums1[i] < nums2[j] ? (nums[k] = nums1[i], i+=1) : (nums[k] = nums2[j], j+=1); k+=1
        }
        while i < nums1.count { nums[k] = nums1[i]; i+=1; k+=1 }
        while j < nums2.count { nums[k] = nums2[j]; j+=1; k+=1 }

        let h = nums.count/2
        return nums.count&1 == 1 ? Double(nums[h]) : Double(nums[h-1]+nums[h])/2.0
    }
}

Find K-th Smallest Pair Distance

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    func smallestDistancePair(_ nums: [Int], _ k: Int) -> Int {
        let nums = nums.sorted()
        var l = 0, h = nums.last!-nums.first!
        while l < h {
            let m = (l+h)/2
            var count = 0, l1 = 0
            for r1 in 0..<nums.count {
                while (nums[r1]-nums[l1]) > m { l1 += 1 }
                count += r1-l1
            }
            count >= k ? (h = m): (l = m+1)
        }
        return l
    }
}

Split Array Largest Sum

1