Problem Statement
Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
You may assume no duplicates in the array.
Here are few examples.
[1,3,5,6], 5 → 2
[1,3,5,6], 2 → 1
[1,3,5,6], 7 → 4
[1,3,5,6], 0 → 0
Original LeetCode problem page
My Solution in Swift
I employed a binary search to find a given target value in a given sorted array. This results in an O(log n) solution.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
func searchInsert(A: [Int], target: Int) -> Int { var leftIndex = 0, rightIndex = A.count - 1, midIndex: Int do { midIndex = (leftIndex + rightIndex) / 2 if target == A[midIndex] { return midIndex } else if target < A[midIndex] { rightIndex = midIndex - 1 } else { leftIndex = midIndex + 1 } } while (leftIndex <= rightIndex) return leftIndex } |
Try It Yourself
1: each links to a blog post of mine that is dedicated to the problem
2: total execution time of a solution on my MacBook Pro (Late 2013, 2.6 GHz Intel Core i7, 16 GB 1600 MHz DDR3). Each solution is compiled with following command:
$ swiftc -O -sdk `xcrun --show-sdk-path --sdk macosx` json.swift main.swift -o mySolution
The total execution time is the average of 10 runs.
3: these test cases are semi-automatically :P retrieved from LeetCode Online Judge system and are kept in JSON format
4: each Xcode project includes everything (my Swift solution to a problem, its JSON test cases and a driver code to test the solution on those test cases)
| Problem1 | Time2 | Test Cases3 | My Xcode Project4 |
| Search Insert Position | 0.002ms |