FeiYan

网站导航

搜索

腾讯微博 新浪微博 FeelBLog 开源中国社区

二分查找(折半查找)算法

2012-09-29 13:37:50     6个评论     7365次访问

前几天去某公司面试被问到这个算法,紧张下写出了以前写过的python猜数字的算法,被狂鄙视,严重影响我在编程圈的前途啊,^_^。之前写过的python猜数字代码如下:

#!/usr/bin/env python
   
#guess a number between 1-100
#if it is smaller ,tell you smaller
#if it is bigger,just tell you are wrong
   
from random import randint
   
num = randint(1,100)
count = 0
   
while 2 > 1:
    count += 1
    number = int(raw_input('input the number:'))
    if number == num:
        print 'good!'
        print '\n'
        print count
        print 'times'
        break
    else: 
        if number < num and flag:
            print 'smaller'
        else:
            print 'bigger'

严格来说这只是二分算法的思路,至于算法精髓我只了解个大概,详细的基本上忘了,所以因为这些算法题我反应比较慢,被无情的PK掉了,\(^o^)/~。回来后心有不甘,用PHP重写二分查找(折半查找)算法,下面的代码是根据我面试时候的思路扩展出来的:

/**
 * @param array $arr 有序数组
 * @param int $x 查找的数值
 */
function erfenSearch( $arr, $x ) {
    $flag = 1;
    $total = count( $arr );
    $left = 0;
    $right = $total-1;
    $key = floor ( ($left+$right)/2 );
    $limit = ceil(log($total,2));
    while( !isset($arr[$key]) || $arr[$key] != $x ){
        if( $arr[$key]>$x ){
            $right = $key;
            $key = floor( ($left+$right)/2 );
        } else {
            $left = $key;
            $key = ceil( ($left+$right)/2 );
        }
        $flag++;
        if( $flag > $limit ){
            echo $x . ' 不在被查询的数组中'."\n";
            return;
        }
    }
    echo '数字' .$x. '在数组中的第 '.($key+1).' 个,查找次数:' . $flag . ' 次。' ."\n";
    return;
}

按照二分查找算法,假设数组有n个元素,最多查找次数是不小于以2为底数的n的对数的数,测试结果没问题,可能代码有点罗嗦,下面的代码是网上搜索到的别人的二分查找算法,比较简单:

function erfenSearch2( $arr, $x ) {
    $l = count($arr);//获得有序数组长度
    $low = 0;
    $high = $l -1;
    $flag = 1;
    while($low <= $high){
        $middle = floor(($low + $high) / 2);
        if($arr[$middle] == $x){
            echo '数字 ' . $x .' 在数组中'.',查找次数:' . $flag . " 次。<br/>\n";
            return $middle;
        } elseif ( $arr[$middle] > $x ) {
            $high = $middle - 1;
        } else {
            $low = $middle + 1;
        }
        $flag++;
    }
    return -1;
}

文章标签: php  python  算法 

本文地址:二分查找(折半查找)算法

相关文章

2009-08-20:常用PHP类建站程序和源码

2009-11-06:PHP中出现Notice: Undefined index的三种解决办法

2011-01-09:PHP转换IP地址到真实地址

2011-11-03:PHP转换汉字拼音和Unicode

2011-11-29:EditPlus 3.x 配置PHP开发环境

2012-08-17:用PHP开发一个自己的博客

2012-09-03:高性能网站架构基础篇

2012-09-17:常用PHP正则表达式

2012-09-17:Ubuntu编译Yaf

2012-09-19:使用Pecl或Pear安装PHP扩展

6 Comments »

  1. liyaohuihuiliyaohuihui
    算法设计经常自己也会看!但是总体数学不好!学的不是太好!

    @飞晏: 我被算法问题坑了一次,长记性了得~// @Anshao微博客: 数学不好..看简单算法都看不懂..

    2013-06-26 16:59:45   

  2. 小谭小谭
    一长串符号……

    2012-10-08 13:47:39   

  3. thinkCuthinkCu
    哈哈,给力呀

    2012-10-03 23:57:58   

  4. 所谓刚子所谓刚子
    技术不行,看不懂算法!

    2012-10-02 11:10:40   

  5. 飞晏飞晏
    我被算法问题坑了一次,长记性了得~

    @Anshao微博客: 数学不好..看简单算法都看不懂..

    2012-09-29 15:53:29   

  6. Anshao微博客Anshao微博客
    数学不好..看简单算法都看不懂..

    2012-09-29 14:26:09   

发布评论

最新评论

  1. 像蛋哥一样抛弃博客好多年的天涯像蛋哥一样抛弃博客好多年的天涯

    蛋哥,PHP-7.1中mcrypt扩展已被废弃了,还用途广泛个蛋蛋啊,赶紧更新吧。

  2. SpecsSpecs

    不错~~

  3. zhyzhy

    我也遇到这个问题 不知道是swf 、jcrop 、 uploadify 还是浏览器缓存