Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
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)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.