Swift 3.0
//
// E_35_SearchInsertPosition.swift
// AlgorithmLeetCode
//
// Created by okerivy on 2017/3/9.
// Copyright ? 2017年 okerivy. All rights reserved.
//
import Foundation
// MARK: - 題目名稱: 35. Search Insert Position
/* MARK: - 所屬類別:
標簽: Array, Binary Search
相關(guān)題目:
(E) First Bad Version
*/
/* MARK: - 題目英文:
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
*/
/* MARK: - 題目翻譯:
給定排序的數(shù)組和目標值，如果找到目標玷禽，則返回索引健提。如果沒有丰捷，返回索引轰传，如果它被插入順序冰沙。
您可以假定數(shù)組中沒有重復架诞。
這里有幾個例子闪金。
[1,3,5,6], 5 → 2
[1,3,5,6], 2 → 1
[1,3,5,6], 7 → 4
[1,3,5,6], 0 → 0
*/
/* MARK: - 解題思路:
這題要求在一個排好序的數(shù)組查找某值value，如果存在則返回對應index瞳腌，不存在則返回能插入到數(shù)組中的index（保證數(shù)組有序）绞铃。
對于不存在的情況，我們只需要在數(shù)組里面找到最小的一個值大于value的index嫂侍，這個index就是我們可以插入的位置儿捧。譬如[1, 3, 5, 6]，查找2挑宠，我們知道3是最小的一個大于2的數(shù)值菲盾，而3的index為1，所以我們需要在1這個位置插入2各淀。如果數(shù)組里面沒有值大于value懒鉴，則插入到數(shù)組末尾。
我們采用二分法解決
典型的二分查找算法碎浇。二分查找算法是在有序數(shù)組中用到的較為頻繁的一種算法临谱，
在未接觸二分查找算法時咆畏，最通用的一種做法是，對數(shù)組進行遍歷吴裤，跟每個元素進行比較，其時間為O(n)溺健。
但二分查找算法則更優(yōu)麦牺，可在最壞的情況下用 O(log n) 完成搜索任務。
譬如數(shù)組 {1鞭缭，2剖膳，3，4岭辣，5吱晒，6，7沦童，8仑濒，9}，查找元素6偷遗，用二分查找的算法執(zhí)行的話墩瞳，其順序為：
第一步查找中間元素，即5氏豌，由于 5 < 6 喉酌，則6必然在5之后的數(shù)組元素中，那么就在{6泵喘，7泪电，8，9}中查找纪铺，
尋找 {6, 7, 8, 9} 的中位數(shù)相速，為7，7 > 6霹陡，則6應該在7左邊的數(shù)組元素中和蚪，那么只剩下6，即找到了烹棉。
二分查找算法就是不斷將數(shù)組進行對半分割攒霹，每次拿中間元素和 target 進行比較。
*/
// FIXME: 沒有完成
/* MARK: - 復雜度分析:
*/
// MARK: - 代碼:
private class Solution {
func searchInsert(_ nums: [Int], _ target: Int) -> Int {
var low = 0
var high = nums.count - 1
// 二分查找 查找第一個出現(xiàn)的元素
// low = high = nums.count - 1 的時候 證明沒有找到
while low < high {
// 直接使用(high + low)/2 可能導致溢出
let mid = (high - low) / 2 + low
if nums[mid] < target {
low = mid + 1
} else {
high = mid
}
}
// 對邊界進行判斷
// 走出while 循環(huán) row = high 需要的是讓 target <= nums[row] 這樣才能插入
// 但是 對于需要插入一個大于數(shù)組中最大的數(shù) 來說 這個時候 nums[row] 依然小于 target
// 需要插入到最后面
if nums[low] < target {
low += 1
}
// 如果 while low <= high { 那么上面這個if 判斷就不需要了
return low
}
}
// MARK: - 測試代碼:
func searchInsertPosition() {
let nums1 = [1,2,3,5,6,6,6,8]
print(Solution().searchInsert(nums1, 8)) // 7
print(Solution().searchInsert(nums1, 2)) // 1
print(Solution().searchInsert(nums1, 6)) // 4
print(Solution().searchInsert(nums1, 7)) // 7
print(Solution().searchInsert(nums1, 0)) // 0
}
