LeetCode Binary Search

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)/2
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)/2
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)/2
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
16
class Solution {
func intersect(_ nums1: [Int], _ nums2: [Int]) -> [Int] {
var dict = [Int: Int]()
var ans = [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

Translated by gpt-3.5-turbo