-
Notifications
You must be signed in to change notification settings - Fork 0
/
RotatedArraySearch.swift
62 lines (55 loc) · 2.08 KB
/
RotatedArraySearch.swift
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
//
// RotatedArraySearch.swift
//
//
// Created by Stefan Jaindl on 21.09.20.
//
import Foundation
open class RotatedArraySearch<T: Comparable> {
public init() { }
open func search(array: [T], searched: T) -> Int? {
guard !array.isEmpty else {
return nil
}
return search(array: array, searched: searched, low: 0, high: array.count - 1)
}
private func search(array: [T], searched: T, low: Int, high: Int) -> Int? {
let center = low + (high - low) / 2
if array[center] == searched {
return center
}
if high <= low {
return nil
}
//search for ordered half
if array[low] < array[center] {
//left half is ordered
if array[low] <= searched && searched <= array[center] {
//within left range
return search(array: array, searched: searched, low: low, high: center - 1)
} else {
//not within left range - search right
return search(array: array, searched: searched, low: center + 1, high: high)
}
} else if array[high] > array[center] {
//right half is ordered
if array[center] <= searched && searched <= array[high] {
//within right range
return search(array: array, searched: searched, low: center + 1, high: high)
} else {
//not within right range - search left
return search(array: array, searched: searched, low: low, high: center - 1)
}
} else {
//could be on both sides
if array[high] != array[center] {
return search(array: array, searched: searched, low: center + 1, high: high)
} else {
if let result = search(array: array, searched: searched, low: center + 1, high: high) {
return result
}
return search(array: array, searched: searched, low: low, high: center - 1)
}
}
}
}