适合小白的python算法-双指针问题PythonTianYao-

一、数组合并

1. 使用模拟指针和并两个有序数组

# 使用指针合并两个数组 arr1 = [1,3,4,6,7]  arr2 = [2,5,8,9,10] #定义两个有序数组，并初始化赋值 ind = 0 # ans比较时的角标 ans = arr1.copy() #ans 排序结果初始化为arr1 for i in range(0,len(arr2)): while ind < len(arr1): if arr2[i]<= arr1[ind]: #范围小于数组的元素下标的最大值    ans.insert(ind + i ,arr2[i]) #向第一非数组中插入第二个数组中的数字 break #跳出当前循环 else:    ind +=1 #ind指向的数字小于i指向的数字，ind向后移动一位 else:   ans =ans +arr2[i:] #ans加上arr2中剩余的元素 break print(ans,type(ans)) #输出结果： [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] <class 'list'> 

2.模拟指针说明：

- 指针：内存空间变量，可以通过一个数组中的没个元素的下标找出它的值， 即存储这个元素位置的变量可以看作一个指针，即python中模拟指针问题 - 实例中 ind是存储数组中数值的下角标的变量，ans用于存储排序完成后数组中的变量 - 使用for循环是因为同一个数字前面可能插入两个及以上的数字， - python中的数组和列表时一个概念，我们这里不区分， 

二、二分法（折半查找法）

1.有序数组的二分法查找

# 有序数组的二分法查找 number = [1,2,3,4,5,6,7,8,9,10,11,12] #初始化定义一个数组 head = 0 #定义指针头 tail =len(number) #定义指针的尾 #数组的长度是最大下标数加1 search = int(input('请输入要搜索的数字：')) while  tail - head >1:  mid = (head + tail ) // 2 #通过整除，找出中间角标  if search < number[mid]:   tail =mid  if  search > number[mid]:   head= mid   if search == number[mid]:   ans =mid    break else : if search == number[head-1]:   ans = head  else :   ans = -1 #数组不存在搜索的数字 if ans == -1: print(search,'不在数组中') else: print(search,'在数组中的索引位置为：',ans) 

2. 二分法说明

二分法又叫折半查找法，每次查找后，查找范围都折半，这样查找到最后，查找范围只剩一个数字时判断是否是查找的数字，如果是记录位置，如果不是，则要查找的数字不在这个数组中，

三、链表（双链表和单链表区别）

链表：是用指针连接的用于存储数据的数组，它最大的优点是在于可以有效地利用零碎的内存空间。在很多语言中，数组的大小要提前定义，定义后不能随便更改，而数组中只能存储同一类型的变量。如果使用了链表，则可以改变数组长度，并且可以在同一数组中存储不同类型的元素。
这和python的列表很像，实际上列表的工作原理就是链表，于是Python语言没有指针，我们使用么你指针的办法实现链表。
单链表：链表的每个元素不仅仅存储各个元素的值。还要存储这个元素的指针值。这样链表才能被连接起来。单链表的每个元素包含本身值和一个指向下一个数的指针，因为链表的最后一个数没有。下一个数，所以它的指针为空。

双链表：双链表中的元素由两个指针和元素值组成，一个指针指向下一个元素，一个指针上一个元素双链表可以双向遍历，无论遍历到第几个数都可以通过索引返回。我们也可以实现双向输出，

注意:指针是存储下一个元素位置的变量，
python中没有指针，链表我们不使用python模拟，这里我们了解单链表和双链表的区别就可以了，这里我们主要介绍概念性东西，让我们整个算法知识体系完整。