Swift实现常用查找算法

search.swift

//
//  main.swift
//  find
//
//  Created by jackyshan on 2018/8/13.
//  Copyright © 2018年 jackyshan. All rights reserved.
//

import Foundation

print("Hello, World!")

func orderFind(_ items: [Int], item: Int) -> Int {//顺序查找
    for i in 0..<items.count {
        if item == items[i] {
            return i+1
        }
    }
    
    return 0
}

func orderFindOptimiz(_ items: [Int], item: Int) -> Int {//顺序查找优化
    var list = items
    list.append(item)//添加的末尾，当做哨兵
    
    var i = 0
    while list[i] != item {//找不到item，i索引往右移动
        i += 1
    }
    
    if i == list.count-1 {//移动到最后哨兵位置，说明没找到，返回0
        return 0
    }
    
    return i+1//返回找到的索引
}

func halfFind(_ items: [Int], item: Int) -> Int {//二分查找
    var low = 0
    var high = items.count - 1
    
    while low < high {
        let mid = (low+high) / 2//计算中间索引
        if item > items[mid] {//大于中间索引，low往右移动
            low = mid + 1
        }
        else if item < items[mid] {//小于中间索引，high往左移动
            high = mid - 1
        }
        else {
            return mid + 1//返回找到的索引
        }
    }
    
    return 0//没找到返回0
}

func InterpolationFind(_ items: [Int], item: Int) -> Int {//插值查找
    var low = 0
    var high = items.count - 1
    
    while low < high {
        let weight = (item - items[low])/(items[high] - items[low])//计算权重
        let mid = low + weight * (high - low)//计算中间索引
        
        if item > items[mid] {//大于中间索引，low往右移动
            low = mid + 1
        }
        else if item < items[mid] {//小于中间索引，high往左移动
            high = mid - 1
        }
        else {
            return mid + 1//返回找到的索引
        }
    }
    
    return 0//没找到返回0
}

class FibonacciSearch {
    var fibonacciSequence: Array<Int> = []
    
    init() {
        self.fibonacciSequence = createFibonacciSequence()
    }
    
    /// 创建Fibonacci数列，F(n) = F(n-1) + F(n-2)，（n >= 2）
    ///
    /// - returns: 返回创建好的Fibonacci数列
    private func createFibonacciSequence() -> Array<Int> {
        var fibonacciSequence = [0, 1];
        for i in 2..<12 {
            fibonacciSequence.append(fibonacciSequence[i-1] + fibonacciSequence[i-2])
        }
        print("Fibonacci数列：\(fibonacciSequence)")
        return fibonacciSequence
    }
    
    
    /// 寻找number在Fibonacci数列中的位置
    ///
    /// - parameter number:
    ///
    /// - returns: 位置索引
    private func findNumberInFibonacci(number: Int) -> Int {
        var index = 0
        while number >= fibonacciSequence[index] {
            index += 1
        }
        return index
    }
    
    
    /// 查找表的元素补齐，便于使用Fibonacci数列进行分割
    ///
    /// - parameter items: 查找表
    /// - parameter key:   补齐后的元素个数
    ///
    /// - returns: 可以进行Fibonacci数列分割的查找表
    private func createFibonacciSearchTable(items: Array<Int>, key: Int) -> Array<Int> {
        var searchItems = items
        for _ in 0..<(fibonacciSequence[key]-items.count) {
            searchItems.append(items.last!)
        }
        return searchItems
    }
    
    func search(items: Array<Int>, item: Int) -> Int {
        //寻找元素的个数在Fibonacci数列中对应区间的位置
        var key = findNumberInFibonacci(number: items.count)
        var searchItems = createFibonacciSearchTable(items: items, key: key)
        
        //查找数据
        var low = 0
        var high = items.count - 1
        while low <= high {
            //
            //前半部分元素的个数为F(key - 1),那么后半部分元素的个数自然就为F(key - 2)
            let mid = low + fibonacciSequence[key - 1] - 1
            if item < searchItems[mid] {
                high = mid - 1
                key = key - 1       //因为查找范围的个数为F(key - 1)，所以更新key的值为key-1
            } else if (item > searchItems[mid]) {
                low = mid + 1
                key = key - 2       //此刻查找范围的元素个数为F(key - 2),更新key的值
            } else {
                if mid < items.count {
                    return mid + 1
                } else {
                    return items.count
                }
            }
        }
        return 0
    }
    
}

//let orderNum = FibonacciSearch.init().search(items: [1,2,3,4,5], item: 3)
//print(orderNum)

func searchMax(length: Int) -> Int {//动态规划求出绳子截取两端的最大乘积
    if length == 0 {
        return 0
    }
    
    if length == 1 {
        return 0
    }
    
    if length == 2 {
        return 1
    }
    
    if length == 3 {
        return 2
    }
    
    var pds: [Int] = [0, 1, 2, 3]+[Int].init(repeating: 0, count: length - 3)
    
    for i in 4...length {
        var max = 0
        
        for j in 1...i/2 {
            let pd = pds[j] * pds[i-j]
            if max < pd {
                max = pd
            }
            
            pds[i] = max
        }
    }
    
    let max = pds[length]
    return max
}

//let max = searchMax(length: 11)
//print(max)

func searchMaxOne(length: Int) -> Int {//贪婪算法除以3，求出3的乘积
    if length == 0 {
        return 0
    }
    
    if length == 1 {
        return 0
    }
    
    if length == 2 {
        return 1
    }
    
    if length == 3 {
        return 2
    }

    var times = length/3
    
    if length - times*3 == 1 {
        times -= 1
    }
    
    let timet = (length - times*3)/2

    return Int(truncating: pow(3, times) as NSDecimalNumber) * Int(truncating: pow(2, timet) as NSDecimalNumber)
}

//let max = searchMaxOne(length: 4)
//print(max)

func searchOneTime(num: Int) {//求出一个二进制包含的1的次数
    var flag: Int = 1
    var count: Int = 0
    
    while flag != 0 {
        if num & flag != 0 {
            count += 1
        }
        flag = flag << 1//往左移一位，继续比较与运算
    }
    
    print(count)
}

//searchOneTime(num: 3)

func searchOneTimet(num: Int) {//求出一个二进制包含的1的次数
    var count = 0
    var n = num
    
    while n != 0 {//不等于0，至少有一个1
        count += 1
        n = n&(n-1)//做与运算把右边比较过的1变为0
    }
    
    print(count)
}

//searchOneTimet(num: 8)

func powH(base: Int, exponent: Int) -> Int {//乘阶
    if exponent == 0 {
        return 1
    }
    
    if exponent == 1 {
        return base
    }
    
    var result = powH(base: base, exponent: exponent >> 1)//除法
    result *= result
    
    if result&1 == 1 {
        result *= base
    }
    
    return result
}

let d = powH(base: 0, exponent: 4)
print(d)