python算法双指针问题:二分查找

这里要注意的是//向下取整,下次循环时,如果大于查找的数字,start+1。

并且,只能向下取整,如果向上取整。

那么,在比较第一个数时,start = 0 。end = 1。mid = 1。就会进入死循环了。

切记切记。

import math
a_list = [2, 5, 23, 45, 67, 89, 90, 123, 234, 345, 567, 7890, 12132]

guess_no = 67
answer = -1

start, end = 0, len(a_list)

while end - start > 1:
    mid = (end + start) // 2
    print(start, end, mid, a_list[mid])
    if a_list[mid] == guess_no:
        answer = guess_no
        break
    elif a_list[mid] < guess_no:
        start = mid + 1
    else:
        end = mid
else:
    if a_list[start] == guess_no:
        answer = guess_no
        print(‘find it‘)

print(answer)
# ==================上面为书,下面为自己=================
answer = -1

start, end = 0, len(a_list)
while start < end:
    mid = math.floor((start + end) / 2)
    print(start, end, mid, a_list[mid])
    if guess_no < a_list[mid]:
        end = mid
    elif guess_no == a_list[mid]:
        answer = guess_no
        break
    else:
        start = mid + 1
print(answer)

输出:

0 13 6 90
0 6 3 45
4 6 5 89
find it
67
0 13 6 90
0 6 3 45
4 6 5 89
4 5 4 67
67

Process finished with exit code 0

原文地址:https://www.cnblogs.com/aguncn/p/10349491.html

时间: 02-03

python算法双指针问题:二分查找的相关文章

【算法拾遗】二分查找递归非递归实现

转载请注明出处:http://blog.csdn.net/ns_code/article/details/33747953 本篇博文没太多要说的,二分查找很简单,也是常见常考的查找算法,以下是递归非递归的实现. 非递归实现: /* 非递归实现,返回对应的序号 */ int BinarySearch(int *arr,int len,int key) { if(arr==NULL || len<1) return -1; int low = 0; int high = len-1; while(l

算法——基础篇——二分查找

     二分查找又称折半查找,优点是比较次数少,查找速度快,平均性能好:其缺点是要求待查表为有序表,且插入删除困难.因此,折半查找方法适用于不经常变动而查找频繁的有序列表.     首先,假设表中元素是按升序排列,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功:否则利用中间位置记录将表分成前.后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表.重复以上过程,直到找到满足条件的记录,使查找成功,或直到子表不存在为止,此时查找不成功

算法题16 二分查找及相关题目

二分查找思想就是取中间的数缩小查找范围,对应不同的题目变形,在取到中间数mid确定下一个查找范围时也有不同,左边界有的low=mid+1,也可能low=mid,右边界有的high=mid-1,也有可能high=mid. 对于一个排序数组来说二分查找的时间复杂度是O(logn) 1. 二分查找法 1 int BinarySearch(int arr[],int len,int target) 2 { 3 if (arr==NULL||len<=0) 4 throw std::exception(&qu

查找算法总结(二分查找/二叉查找树/红黑树/散列表)

1.二分查找 二分查找时,先将被查找的键和子数组的中间键比较.如果被查找的键小于中间键,就在左子数组继续查找,如果大于中间键,就在右子数组中查找,否则中间键就是要找的元素. /** * 二分查找 */ public class BinarySearch { public static int find(int[] array, int key) { int left = 0; int right = array.length - 1; // while (left <= right)不能改为<

python s12 day4 算法基础之二分查找

def binary_search(data_source,find_n): mind=int(len(data_source)/2) if len(data_source)>=1: if data_source[mid]>find_n: print("data in left of [%s]"%sdata_souerce[mid]) //print(data_souerce[:mid]    binary_search(data_source[:mid],find_n)

python函数:递归函数及二分查找算法

本文和大家分享的主要是python的递归函数及二分查找算法相关内容,一起来看看吧,希望对大家学习python有所帮助. 一.递归的定义 def story(): s = """ 从前有个山,山里有座庙,庙里老和尚讲故事, 讲的什么呢? """ print(s) story() story() 老和尚讲故事 递归的定义 -- 在一个函数里再调用这个函数本身.这种魔性的使用函数的方式就叫做 递归 . 递归的最大深度:997 1.python递归最大层

二分查找算法java实现

今天看了一下JDK里面的二分法是实现,觉得有点小问题.二分法的实现有多种今天就给大家分享两种.一种是递归方式的,一种是非递归方式的.先来看看一些基础的东西. 1.算法概念. 二分查找算法也称为折半搜索.二分搜索,是一种在有序数组中查找某一特定元素的搜索算法.请注意这种算法是建立在有序数组基础上的. 2.算法思想. ①搜素过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜素过程结束: ②如果某一特定元素大于或者小于中间元素,则在数组大于或小于中间元素的那一半中查找,而且跟开始一样从中间

算法—8.有序数组中的二分查找

1.具体算法 /** * 算法3.2 二分查找(基于有序数组) * Created by huazhou on 2015/11/29. */ public class BinarySearchST<Key extends Comparable<key>, Value> { private Key[] keys; private Value[] vals; private int N; public BinarySearchST(int capacity){ keys = (Key[

Java冒泡排序和二分查找(预习)

经查阅,将资料整理如下: 一.冒泡排序 1.算法简介 它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来.走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成. 这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端,故名. 2.算法原理 (1)比较相邻的元素.如果第一个比第二个大,就交换他们两个. (2)对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对.在这一点,最后的元素应该会是最大的数. (3)针对所有的元素重复以上的

python算法之二分查找

说明:大部分代码是在网上找到的,好几个代码思路总结出来的 通常写算法,习惯用C语言写,显得思路清晰.可是假设一旦把思路确定下来,并且又不想打草稿.想高速写下来看看效果,还是python写的比較快.也看个人爱好.实习的时候有个同事对于python的缩进来控制代码块各种喷....他认为还是用大括号合适...怎么说呢,适合自己的才是最好的.我个人的毛病就是,写了几天C,到要转到python的时候,代码中依旧有C的影子..比方大括号问题,比方忘记在while或这for.if.else等后面加":&quo