算法基础

二叉树

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
author : bw.ling
create_time : 2022/10/10
本页介绍二分查找的用法
"""
'''
二分查找就是，每次对半查找。例如：猜数字，1-100 以内，猜数字。最快就是猜 7 次就猜到。log2^100 < 7 
'''

# 二分查找的模版
# 解释：就像我们玩猜数字游戏一样，给出 1 - 100 的范围，其中一个人做判官（设置的数字是 37）
# 1 号同学猜 20，那么就比 37 小，接下来的范围就是从 21 到 100 （相当于小值 + 1，大值不变）
# 2 号同学猜 66，那么就比 37 大，接下来的范围就是从 21 到 65 （相当于大值 - 1，小值不变）
# .... 不断循环，直到猜中结果

def binary_search(lists: list, obj):
	"""
	:param lists:给出的一个有序列表
	:param obj: 需要找出的目标值
	:return:
	"""
	low = 0
	high = len(lists) - 1
	while low <= high:
		mid = int((low + high) / 2)
		value = lists[mid]
		if value == obj:
			return mid
		if value < obj:
			low = mid + 1
		else:
			high = mid - 1
	return []


lt = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18]
ob = 18