algorithm/BinarySearch/VagueBinarySearch.swift at master · gl-lei/algorithm · GitHub

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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
//
//  VagueBinarySearch.swift
//  BinarySearch
//
//  Created by ggl on 2019/5/21.
//  Copyright © 2019 ggl. All rights reserved.
//  二分查找变形问题

import Foundation

/// 查找第一个值等于给定值的元素
///
/// - Parameters:
///   - sortedArray: 有序数组
///   - value: 需要查找的值
/// - Returns: 查找到的值的下标
func vagueBinarySearchFirstEqualValueWithSortedArray(_ sortedArray: [Int], value: Int) -> Int {
    var low = 0
    var high = sortedArray.count-1
    while low <= high {
        let mid = low + ((high - low) >> 1)
        if sortedArray[mid] > value {
            high = mid - 1
        } else if sortedArray[mid] < value {
            low = mid + 1
        } else {
            if mid == 0 || sortedArray[mid-1] != value {
                return mid
            }
            high = mid - 1
        }
    }

    return -1;
}

/// 查找最后一个值等于给定值的元素
///
/// - Parameters:
///   - sortedArray: 有序数组
///   - value: 需要查找的值
/// - Returns: 查找到的值的下标
func vagueBinarySearchLastEqualValueWithSortedArray(_ sortedArray: [Int], value: Int) -> Int {
    var low = 0
    var high = sortedArray.count - 1
    while low <= high {
        let mid = low + ((high - low) >> 1)
        if sortedArray[mid] > value {
            high = mid - 1
        } else if sortedArray[mid] < value {
            low = mid + 1
        } else {
            if mid == sortedArray.count-1 || sortedArray[mid+1] != value {
                return mid
            }
            low = mid + 1
        }
    }
    return -1;
}

/// 查找第一个大于等于给定值的元素
///
/// - Parameters:
///   - sortedArray: 有序数组
///   - value: 需要查找的值
/// - Returns: 查找到的值的下标
func vagueBinarySearchFirstGreaterThanOrEqualValueWithSortedArray(_ sortedArray: [Int], value: Int) -> Int {
    var low = 0
    var high = sortedArray.count - 1
    while low <= high {
        let mid = low + ((high - low) >> 1)
        if sortedArray[mid] < value {
            low = mid + 1
        } else {
            if mid == 0 || sortedArray[mid-1] < value {
                return mid
            }
            high = mid - 1
        }
    }
    return -1;
}

/// 查找最后一个小于等于给定值的元素
///
/// - Parameters:
///   - sortedArray: 有序数组
///   - value: 需要查找的值
/// - Returns: 查找到的值的下标
func vagueBinarySearchLastLessThanOrEqualValueWithSortedArray(_ sortedArray: [Int], value: Int) -> Int {
    var low = 0
    var high = sortedArray.count - 1
    while low <= high {
        let mid = low + ((high - low) >> 1)
        if sortedArray[mid] > value {
            high = mid - 1
        } else {
            if mid == sortedArray.count-1 || sortedArray[mid+1] > value {
                return mid
            }
            low = mid + 1
        }
    }
    return -1;
}