8000 Merge pull request #185 from chris-pilcher/binary-search-swift3 · codee/swift-algorithm-club@58bb5ef · GitHub
[go: up one dir, main page]
Skip to content

Commit 58bb5ef

Browse files
author
Chris Pilcher
authored
Merge pull request kodecocodes#185 from chris-pilcher/binary-search-swift3
Binary search swift3
2 parents b55c49f + 20236b2 commit 58bb5ef

File tree

7 files changed

+39
-39
lines changed

7 files changed

+39
-39
lines changed

‎.travis.yml

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -11,7 +11,7 @@ script:
1111
# - xcodebuild test -project ./All-Pairs\ Shortest\ Paths/APSP/APSP.xcodeproj -scheme APSPTests
1212
# - xcodebuild test -project ./Array2D/Tests/Tests.xcodeproj -scheme Tests
1313
- xcodebuild test -project ./AVL\ Tree/Tests/Tests.xcodeproj -scheme Tests
14-
# - xcodebuild test -project ./Binary\ Search/Tests/Tests.xcodeproj -scheme Tests
14+
- xcodebuild test -project ./Binary\ Search/Tests/Tests.xcodeproj -scheme Tests
1515
# - xcodebuild test -project ./Binary\ Search\ Tree/Solution\ 1/Tests/Tests.xcodeproj -scheme Tests
1616
# - xcodebuild test -project ./Bloom\ Filter/Tests/Tests.xcodeproj -scheme Tests
1717
# - xcodebuild test -project ./Bounded\ Priority\ Queue/Tests/Tests.xcodeproj -scheme Tests

‎Binary Search/BinarySearch.playground/Contents.swift

Lines changed: 8 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -7,13 +7,13 @@ let numbers = [11, 59, 3, 2, 53, 17, 31, 7, 19, 67, 47, 13, 37, 61, 29, 43, 5, 4
77
let sorted = numbers.sorted()
88

99
// Using recursive solution
10-
binarySearch(a: sorted, key: 2, range: 0 ..< sorted.count) // gives 0
11-
binarySearch(a: sorted, key: 67, range: 0 ..< sorted.count) // gives 18
12-
binarySearch(a: sorted, key: 43, range: 0 ..< sorted.count) // gives 13
13-
binarySearch(a: sorted, key: 42, range: 0 ..< sorted.count) // nil
10+
binarySearch(sorted, key: 2, range: 0 ..< sorted.count) // gives 0
11+
binarySearch(sorted, key: 67, range: 0 ..< sorted.count) // gives 18
12+
binarySearch(sorted, key: 43, range: 0 ..< sorted.count) // gives 13
13+
binarySearch(sorted, key: 42, range: 0 ..< sorted.count) // nil
1414

1515
// Using iterative solution
16-
binarySearch(a: sorted, key: 2) // gives 0
17-
binarySearch(a: sorted, key: 67) // gives 18
18-
binarySearch(a: sorted, key: 43) // gives 13
19-
binarySearch(a: sorted, key: 42) // nil
16+
binarySearch(sorted, key: 2) // gives 0
17+
binarySearch(sorted, key: 67) // gives 18
18+
binarySearch(sorted, key: 43) // gives 13
19+
binarySearch(sorted, key: 42) // nil

‎Binary Search/BinarySearch.playground/Sources/BinarySearch.swift

Lines changed: 4 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -13,15 +13,15 @@ import Foundation
1313

1414
// The recursive version of binary search.
1515

16-
public func binarySearch<T: Comparable>(a: [T], key: T, range: Range<Int>) -> Int? {
16+
public func binarySearch<T: Comparable>(_ a: [T], key: T, range: Range<Int>) -> Int? {
1717
if range.lowerBound >= range.upperBound {
1818
return nil
1919
} else {
2020
let midIndex = range.lowerBound + (range.upperBound - range.lowerBound) / 2
2121
if a[midIndex] > key {
22-
return binarySearch(a: a, key: key, range: range.lowerBound ..< midIndex)
22+
return binarySearch(a, key: key, range: range.lowerBound ..< midIndex)
2323
} else if a[midIndex] < key {
24-
return binarySearch(a: a, key: key, range: midIndex + 1 ..< range.upperBound)
24+
return binarySearch(a, key: key, range: midIndex + 1 ..< range.upperBound)
2525
} else {
2626
return midIndex
2727
}
@@ -35,7 +35,7 @@ public func binarySearch<T: Comparable>(a: [T], key: T, range: Range<Int>) -> In
3535
uses a while loop, while the other calls itself recursively.
3636
**/
3737

38-
public func binarySearch<T: Comparable>(a: [T], key: T) -> Int? {
38+
public func binarySearch<T: Comparable>(_ a: [T], key: T) -> Int? {
3939
var lowerBound = 0
4040
var upperBound = a.count
4141
while lowerBound < upperBound {

‎Binary Search/README.markdown

Lines changed: 4 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -15,7 +15,7 @@ numbers.indexOf(43) // returns 15
1515
The built-in `indexOf()` function performs a [linear search](../Linear Search/). In code that looks something like this:
1616

1717
```swift
18-
func linearSearch<T: Equatable>(a: [T], _ key: T) -> Int? {
18+
func linearSearch<T: Equatable>(_ a: [T], _ key: T) -> Int? {
1919
for i in 0 ..< a.count {
2020
if a[i] == key {
2121
return i
@@ -45,7 +45,7 @@ Sounds great, but there is a downside to using binary search: the array must be
4545

4646
Here's how binary search works:
4747

48-
- Split the array in half and determine whether the thing you're looking for, known as the *search key*, is in the left half or in the right half.
48+
- Split the array in half and determine whether the thing you're looking for, known as the *search key*, is in the left half or in the right half.
4949
- How do you determine in which half the search key is? This is why you sorted the array first, so you can do a simple `<` or `>` comparison.
5050
- If the search key is in the left half, you repeat the process there: split the left half into two even smaller pieces and look in which piece the search key must lie. (Likewise for when it's the right half.)
5151
- This repeats until the search key is found. If the array cannot be split up any further, you must regrettably conclude that the search key is not present in the array.
@@ -57,7 +57,7 @@ Now you know why it's called a "binary" search: in every step it splits the arra
5757
Here is a recursive implementation of binary search in Swift:
5858

5959
```swift
60-
func binarySearch<T: Comparable>(a: [T], key: T, range: Range<Int>) -> Int? {
60+
func binarySearch<T: Comparable>(_ a: [T], key: T, range: Range<Int>) -> Int? {
6161
if range.lowerBound >= range.upperBound {
6262
// If we get here, then the search key is not present in the array.
6363
return nil
@@ -180,7 +180,7 @@ Binary search is recursive in nature because you apply the same logic over and o
180180
Here is an iterative implementation of binary search in Swift:
181181

182182
```swift
183-
func binarySearch<T: Comparable>(a: [T], key: T) -> Int? {
183+
func binarySearch<T: Comparable>(_ a: [T], key: T) -> Int? {
184184
var lowerBound = 0
185185
var upperBound = a.count
186186
while lowerBound < upperBound {

‎Binary Search/Tests/BinarySearchTests.xcodeproj/project.pbxproj renamed to ‎Binary Search/Tests/Tests.xcodeproj/project.pbxproj

Lines changed: 10 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -12,7 +12,7 @@
1212
/* End PBXBuildFile section */
1313

1414
/* Begin PBXFileReference section */
15-
7B2BBC801C779D720067B71D /* BinarySearchTests.xctest */ = {isa = PBXFileReference; explicitFileType = wrapper.cfbundle; includeInIndex = 0; path = BinarySearchTests.xctest; sourceTree = BUILT_PRODUCTS_DIR; };
15+
7B2BBC801C779D720067B71D /* Tests.xctest */ = {isa = PBXFileReference; explicitFileType = wrapper.cfbundle; includeInIndex = 0; path = Tests.xctest; sourceTree = BUILT_PRODUCTS_DIR; };
1616
7B2BBC941C779E7B0067B71D /* Info.plist */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = text.plist.xml; path = Info.plist; sourceTree = SOURCE_ROOT; };
1717
7B80C3CD1C77A256003CECC7 /* BinarySearchTests.swift */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.swift; path = BinarySearchTests.swift; sourceTree = SOURCE_ROOT; };
1818
7B80C3CF1C77A263003CECC7 /* BinarySearch.swift */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.swift; name = BinarySearch.swift; path = ../BinarySearch.swift; sourceTree = SOURCE_ROOT; };
@@ -40,7 +40,7 @@
4040
7B2BBC721C779D710067B71D /* Products */ = {
4141
isa = PBXGroup;
4242
children = (
43-
7B2BBC801C779D720067B71D /* BinarySearchTests.xctest */,
43+
7B2BBC801C779D720067B71D /* Tests.xctest */,
4444
);
4545
name = Products;
4646
sourceTree = "<group>";
@@ -59,9 +59,9 @@
5959
/* End PBXGroup section */
6060

6161
/* Begin PBXNativeTarget section */
62-
7B2BBC7F1C779D720067B71D /* BinarySearchTests */ = {
62+
7B2BBC7F1C779D720067B71D /* Tests */ = {
6363
isa = PBXNativeTarget;
64-
buildConfigurationList = 7B2BBC8C1C779D720067B71D /* Build configuration list for PBXNativeTarget "BinarySearchTests" */;
64+
buildConfigurationList = 7B2BBC8C1C779D720067B71D /* Build configuration list for PBXNativeTarget "Tests" */;
6565
buildPhases = (
6666
7B2BBC7C1C779D720067B71D /* Sources */,
6767
7B2BBC7D1C779D720067B71D /* Frameworks */,
@@ -71,9 +71,9 @@
7171
);
7272
dependencies = (
7373
);
74-
name = BinarySearchTests;
74+
name = Tests;
7575
productName = TestsTests;
76-
productReference = 7B2BBC801C779D720067B71D /* BinarySearchTests.xctest */;
76+
productReference = 7B2BBC801C779D720067B71D /* Tests.xctest */;
7777
productType = "com.apple.product-type.bundle.unit-test";
7878
};
7979
/* End PBXNativeTarget section */
@@ -92,7 +92,7 @@
9292
};
9393
};
9494
};
95-
buildConfigurationList = 7B2BBC6C1C779D710067B71D /* Build configuration list for PBXProject "BinarySearchTests" */;
95+
buildConfigurationList = 7B2BBC6C1C779D710067B71D /* Build configuration list for PBXProject "Tests" */;
9696
compatibilityVersion = "Xcode 3.2";
9797
developmentRegion = English;
9898
hasScannedForEncodings = 0;
@@ -105,7 +105,7 @@
105105
projectDirPath = "";
106106
projectRoot = "";
107107
targets = (
108-
7B2BBC7F1C779D720067B71D /* BinarySearchTests */,
108+
7B2BBC7F1C779D720067B71D /* Tests */,
109109
);
110110
};
111111
/* End PBXProject section */
@@ -245,7 +245,7 @@
245245
/* End XCBuildConfiguration section */
246246

247247
/* Begin XCConfigurationList section */
248-
7B2BBC6C1C779D710067B71D /* Build configuration list for PBXProject "BinarySearchTests" */ = {
248+
7B2BBC6C1C779D710067B71D /* Build configuration list for PBXProject "Tests" */ = {
249249
isa = XCConfigurationList;
250250
buildConfigurations = (
251251
7B2BBC871C779D720067B71D /* Debug */,
@@ -254,7 +254,7 @@
254254
defaultConfigurationIsVisible = 0;
255255
defaultConfigurationName = Release;
256256
};
257-
7B2BBC8C1C779D720067B71D /* Build configuration list for PBXNativeTarget "BinarySearchTests" */ = {
257+
7B2BBC8C1C779D720067B71D /* Build configuration list for PBXNativeTarget "Tests" */ = {
258258
isa = XCConfigurationList;
259259
buildConfigurations = (
260260
7B2BBC8D1C779D720067B71D /* Debug */,

‎Binary Search/Tests/BinarySearchTests.xcodeproj/project.xcworkspace/contents.xcworkspacedata renamed to ‎Binary Search/Tests/Tests.xcodeproj/project.xcworkspace/contents.xcworkspacedata

File renamed without changes.

‎Binary Search/Tests/BinarySearchTests.xcodeproj/xcshareddata/xcschemes/Tests.xcscheme renamed to ‎Binary Search/Tests/Tests.xcodeproj/xcshareddata/xcschemes/Tests.xcscheme

Lines changed: 12 additions & 12 deletions
Original file line numberDiff line numberDiff line change
@@ -15,9 +15,9 @@
1515
<BuildableReference
1616
BuildableIdentifier = "primary"
1717
BlueprintIdentifier = "7B2BBC7F1C779D720067B71D"
18-
BuildableName = "BinarySearchTests.xctest"
19-
BlueprintName = "BinarySearchTests"
20-
ReferencedContainer = "container:BinarySearchTests.xcodeproj">
18+
BuildableName = "Tests.xctest"
19+
BlueprintName = "Tests"
20+
ReferencedContainer = "container:Tests.xcodeproj">
2121
</BuildableReference>
2222
</BuildActionEntry>
2323
</BuildActionEntries>
@@ -33,9 +33,9 @@
3333
<BuildableReference
3434
BuildableIdentifier = "primary"
3535
BlueprintIdentifier = "7B2BBC7F1C779D720067B71D"
36-
BuildableName = "BinarySearchTests.xctest"
37-
BlueprintName = "BinarySearchTests"
38-
ReferencedContainer = "container:BinarySearchTests.xcodeproj">
36+
BuildableName = "Tests.xctest"
37+
BlueprintName = "Tests"
38+
ReferencedContainer = "container:Tests.xcodeproj">
3939
</BuildableReference>
4040
</TestableReference>
4141
</Testables>
@@ -56,9 +56,9 @@
5656
<BuildableReference
5757
BuildableIdentifier = "primary"
5858
BlueprintIdentifier = "7B2BBC7F1C779D720067B71D"
59-
BuildableName = "BinarySearchTests.xctest"
60-
BlueprintName = "BinarySearchTests"
61-
ReferencedContainer = "container:BinarySearchTests.xcodeproj">
59+
BuildableName = "Tests.xctest"
60+
BlueprintName = "Tests"
61+
ReferencedContainer = "container:Tests.xcodeproj">
6262
</BuildableReference>
6363
</MacroExpansion>
6464
<AdditionalOptions>
@@ -74,9 +74,9 @@
7474
<BuildableReference
7575
BuildableIdentifier = "primary"
7676
BlueprintIdentifier = "7B2BBC7F1C779D720067B71D"
77-
BuildableName = "BinarySearchTests.xctest"
78-
BlueprintName = "BinarySearchTests"
79-
ReferencedContainer = "container:BinarySearchTests.xcodeproj">
77+
BuildableName = "Tests.xctest"
78+
BlueprintName = "Tests"
79+
ReferencedContainer = "container:Tests.xcodeproj">
8080
</BuildableReference>
8181
</MacroExpansion>
8282
</ProfileAction>

0 commit comments

Comments
 (0)
0