二分查找算法

代码解释

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

def binary_search(arr, target, left, right):
    # 基线条件：搜索区间无效
    if left > right:
        return -1
    
    mid = (left + right) // 2
    
    # 基线条件：找到目标值
    if arr[mid] == target:
        return mid
    # 递归条件：目标值在左半部分
    elif arr[mid] > target:
        return binary_search(arr, target, left, mid - 1)
    # 递归条件：目标值在右半部分
    else:
        return binary_search(arr, target, mid + 1, right)

我的解释

其实这里的算法解释和上次学习的递归关系很大

而且我感觉，大部分的数学问题都可以使用递归解决，这本来就是一种数学思想

分而治之 ！！！这就是数学思想

这里的markdown的语法来自菜鸟教学

还有就是分享周杰伦的歌真的很好听

快速排序

D&C

这里是对D&C的解释:

归并排序（Merge Sort）
将数组分成两半，递归排序，再将两个有序数组合并。

快速排序（Quick Sort）
选择一个基准元素，将数组分为小于基准和大于基准的两部分，递归排序。

二分查找（Binary Search）
将有序数组分为两半，递归查找目标值。

大整数乘法
将大整数分解为更小的部分，递归计算后再合并结果。

矩阵乘法（Strassen算法）
将矩阵分解为子矩阵，递归计算后再合并。

最近点对问题
将平面上的点集分为两半，递归求解最近点对，再合并结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

def merge_sort(arr):
    # 基线条件：数组长度为1或0时直接返回
    if len(arr) <= 1:
        return arr
    
    # 分解：将数组分为两半
    mid = len(arr) // 2
    left_half = merge_sort(arr[:mid])  # 递归解决左半部分
    right_half = merge_sort(arr[mid:])  # 递归解决右半部分
    
    # 合并：将两个有序数组合并
    return merge(left_half, right_half)

def merge(left, right):
    result = []
    i = j = 0
    # 合并两个有序数组
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    # 将剩余部分加入结果
    result.extend(left[i:])
    result.extend(right[j:])
    return result

1
2
3
4
5
6
7
8
9

def quicksort(array): 
    if len(array) < 2: 
        return array 
    else: 
        pivot = array[0] 
        less = [i for i in array[1:] if i <= pivot] 
        greater = [i for i in array[1:] if i > pivot] 
    return quicksort(less) + [pivot] + quicksort(greater) 
print quicksort([10, 5, 2, 3]) 

先设置一个基准值[pivot]然后以此为基准分为大于和小于的两个子集合，对子集合再进行递归运算。

刚才你大致见识了归纳证明！归纳证明是一种证明算法行之有效的方式，它分两步：基线
条件和归纳条件。是不是有点似曾相识的感觉？例如，假设我要证明我能爬到梯子的最上面。
递归条件是这样的：如果我站在一个横档上，就能将脚放到下一个横档上。换言之，如果我站
在第二个横档上，就能爬到第三个横档。这就是归纳条件。而基线条件是这样的，即我已经站
在第一个横档上。因此，通过每次爬一个横档，我就能爬到梯子最顶端。
对于快速排序，可使用类似的推理。在基线条件中，我证明这种算法对空数组或包含一个
元素的数组管用。在归纳条件中，我证明如果快速排序对包含一个元素的数组管用，对包含两
个元素的数组也将管用；如果它对包含两个元素的数组管用，对包含三个元素的数组也将管用，
以此类推。因此，我可以说，快速排序对任何长度的数组都管用。这里不再深入讨论归纳证明，
但它很有趣，并与D&C协同发挥作用

以上是我在学习过程中向ai提问的问题!!!

 二分查找的速度比简单查找快得多。
 O(log n)比O(n)快。需要搜索的元素越多，前者比后者就快得越多。
 算法运行时间并不以秒为单位。
 算法运行时间是从其增速的角度度量的。
 算法运行时间用大O表示法表示。

这个是小结

对于这一节的理解，最好的就是，一个算法的O()的计算是执行程序次数和单次程序时间决定的。

其中呢，二分算法是很快的一种算法了，在我所学之中。

推而广之，涉及n个城市时，需要执行n!（n的阶乘）次操作才能计算出结果。因此运行时间
为O(n!)，即阶乘时间。除非涉及的城市数很少，否则需要执行非常多的操作。如果涉及的城市
数超过100，根本就不能在合理的时间内计算出结果——等你计算出结果，太阳都没了

还有就是代数上给予程序执行总时间的线性变化和非线性变化。

 O(log n)，也叫对数时间，这样的算法包括二分查找。
 O(n)，也叫线性时间，这样的算法包括简单查找。
 O(n * log n)，这样的算法包括第4章将介绍的快速排序——一种速度较快的排序算法。
 O(n**2 )，这样的算法包括第2章将介绍的选择排序——一种速度较慢的排序算法。
 O(n!)，这样的算法包括接下来将介绍的旅行商问题的解决方案——一种非常慢的算法。

如果使用循环，程序的性能可能更高；如果使用递归，程序可能
更容易理解。如何选择要看什么对你来说更重要。

在你看来，哪种方法更容易呢？第一种方法使用的是while循环：只要盒子堆不空，就从中
取一个盒子，并在其中仔细查找。
def look_for_key(main_box):
pile = main_box.make_a_pile_to_look_through()
while pile is not empty:
box = pile.grab_a_box()
for item in box:
if item.is_a_box():
pile.append(item)
elif item.is_a_key():
print “found the key!”
第二种方法使用递归——函数调用自己，这种方法的伪代码如下。
def look_for_key(box):
for item in box:
if item.is_a_box():
look_for_key(item)
elif item.is_a_key():
print “found the key!”

其实递归我早就学习过了，这里就随便写写算了。

每个递归函数都有两部分：基线
条件（base case）和递归条件（recursive case）。递归条件指的是函数调用自己，而基线条件则
指的是函数不再调用自己，从而避免形成无限循环。

这个说法是我很精简

def countdown(i):
print i
if i <= 0:
return
else:
countdown(i-1)

其实就是➕了if else了。

递归和栈是有很大联系的，主要是栈是入的人出，这就导致一个条件，

递归解决一个问题，要分情况要不解决，要不就是在次调用这个方法，在方法种解决问题。

这就和栈，先进入解决问题后，就倒序出栈，这就是栈和递归之间的关系。

今天的博客

今天是我的生日哈哈哈，相信世界上还有很多人和我一样来庆祝这天。

祝你们生日快乐，我未知的朋友们，虽然我们几乎永远不能相见。

其实我想在这一天一个人自娱自乐的，可惜我的英语挂科了。

其实我在高中时期就开始不那么关注生日啦，但是最近我仔细思考，我想我们的生日，大概率就只有父母和自己才最清楚。我其实大概不太记得我的父母的生日。

我很庆幸我的父母记得我的生日，我很感谢他们。我之前读过太多关于原生家庭的书，我开始追求摆脱一切有关原生家庭的糟粕。

但糟粕和蜜糖在我们的相处中是难以区分的。

我为我可以独立的完成某种神秘的仪式来度过我的二十一岁而高兴。

我相信我在取悦自己，😄😄😄我喜欢这种感觉，像极了我小时候自己一个人玩乐高的时候，感谢乐高，哈哈哈哈哈哈。没有他们真的会给我造成很大麻烦的，我恐怕会无聊死。

今天有人给我买蛋糕，但我拒绝啦。我可能害怕破坏我自己创造的神秘仪式。也就是我自娱自乐的情趣，如果有人来参与这个过程我恐怕会觉得我的秘密活动被人猜透了，哈哈哈在这方面我还真的很有趣呢。

送我蛋糕，
我说不要，
和我说我送你啦，你不拿是你的事情。
她应该知道我不会浪费，哈哈哈哈哈。
看来我的秘密计划被人识破了，好难受啊。
她可真是拿准我了，我无所谓啦，但是我讨厌，我要说我不喜欢。
讨厌自己的计划被人无情的打破🐸

贴一张我最喜欢的动漫Eva的图片!!!

故事

小故事:在一个很偏远的村庄,故事发生在这个村庄的坡上。

灰色和红色的流沙，铺满了这个世界，太阳是红色的，黑色的颗粒，在这里飞舞。

在这个村庄中的四个方向和天空还有地里世界中存在六个可怕的存在。

他们是这个世界规则，错乱之后的存在，也许是世界诞生之前就存在的。

这里有哥特式的尖顶琼楼，还有英国基督教的教堂，当然还有道观还有寺庙。

他们赫然独立于黑纱之中，这些建筑将黑纱撑开，开辟了红色的光。

一个穿着僧人衣着的青年光头从寺庙里走了出来，与此同时在小光头走出来后，道观里的道士也走了出来。

这个道士留着长长的胡子，拿着像是小型拖把一样的法器。

小和尚对道士说，听说你们的天师把西边那个奇异生物杀死了？

小和尚一边说一边挑着眉似乎是在试探着这个道士。

道士可不吃这一套，道士撇眼看向小和尚，心里估计嘀咕着这小光头，也太不了解道士了吧。

嗤笑到，你们家的菩萨可不比我们的天师弱啊，相传菩萨摆渡众生。

在这个可怕的世界，人们开始在宗教中获得力量。来对抗六只奇异带来的破坏。

小和尚沉默不语，深沉地看着道士，看着道士那一脸鄙夷，最讨人厌的是他的右手中指在抠鼻子。

小和尚快破防了，如果他们的世界有破防二字。

一个穿着破烂衣服的农民来到小和尚和道士身边，小和尚很明显有点嫌弃这个农民。他长得很黑，估计这小和尚会觉得他从出生就开始这么黑。

农民憋着令人不适的微笑，讨好地向小和尚和道士说道，多亏了你们我们才可以无忧地耕地。

小和尚率先回道:”都是我们菩萨心善，来消灭苦难，鼓励大家努力工作，追求下一世的富足和安宁，而我们的菩萨会摆渡你们。”

道士笑而不语

突然间，东南西北地里天上，黑色的力量，形成浓郁的黑色液体包裹着这个世界的天空，连红色的太阳也消失了

一切开始消散，变成碎片粉末，连同小和尚和道士神秘的笑容，以及农民奇怪的笑容。

突然我的梦醒了哈哈哈哈哈哈哈

(以上都是昨天晚上做的梦，切勿当真😄)

我学习计算机已经一年半了，

我为此高兴，庆祝这个时刻，

明天是我的生日。

title:对于最近生活的想法

时间过的很快，离我高中毕业以后，在之后的两年中，我越来越怀念我的高中生活了。

我很怀念我的朋友们，我在之前总是觉得，初中的我才是最好的。（因为我在那段时间获得了大部分人的尊重。）

我只是想说我很思念我的高中，经此而已，但完全不是高中那些压力巨大的我。我们曾经拥有很多美好的片刻，我现在还是可以清晰的想到那些时刻。

我要记录下来，我要让大家看到我的想法。

这也是我做这个博客的想法，我其实是一个不擅长用口头语言，来表达想法的人。

还有就是谢谢我的父母。尤其是我的父亲，也许我的话很苛刻，我在伤害他，但是我没法在他面前说这些。

也只有每个月的几天我才会如此感性，我乐于把我感性的一面记录在这里。

祝大家生活愉快

博客

希望我的日记可以和github的服务器一样很久很久地存在在这个世界上

我相信没有什么比这个更加值得高兴的啦

我会认真地记录我的生活，在这个完全未知的世界

如果在未来很多年后还有人能看到我写的东西，写的一些很平常很平凡的日记，我不是为了获得什么东西。

当然也不是成为作家，我想我还太年轻了，对于成为作家。

我会写一些书的书评，我得记录下来，我害怕我在很多年后不会思考，那是多么可怕。

也许是因为害怕，这里会成为我倾诉的地方，因为你们都是与我不相关的一群朋友。

我一想到这里我就高兴，没有什么比和未知的人交朋友更加开心啦。

我会记录时间，同时时间也在记录着我，和你们的故事。

我也会记录你们的故事，如果你乐于和我分享。

这里是hinder110的博客。