算法:二分查找

用PHP实现二分查找

// 二分法查找 by SR.李

// 数组必须为有序数组
$arr = [1,2,3,4,5,6,7,8,9,10,11];

function dichotomySearch($arr, $searchValue)
{
    $count = count($arr);
    $min = 0;
    $max = $count - 1;
    // 范围判断
    if ($arr[$max] < $searchValue || $arr[$min] > $searchValue) {
        return '要寻找的值不在数组里';
    }
    while (true) {
        $middle = (int) (($max + $min)/2);
        if ($arr[$middle] > $searchValue) {
            $max = $middle;
        } else {
            $min = $middle;
        }
        // 找到后返回
        if ($arr[$middle] == $searchValue) {
            return $middle;
        }
    }
}

echo dichotomySearch($arr, 3);

用golang实现

package main

import "fmt"

var arr = [...]int{
    1,
    2,
    3,
    4,
    5,
}

func main() {
    key := dichotomySearch(arr, 100)
    if key == -1 {
        fmt.Println("查找的值不存在数组里")
        return
    }
    fmt.Println("要查找的值的键为:", key)
}

func dichotomySearch(arr [5]int, searchValue int) int {

    var count int = len(arr)
    var min int = 0
    var max int = count - 1
    var middle int
    // 范围判断
    if arr[max] < searchValue || arr[min] > searchValue {
        return -1
    }
    for {
        middle = int((max + min) / 2)
        if arr[middle] > searchValue {
            max = middle
        } else {
            min = middle
        }
        // 找到后返回
        if arr[middle] == searchValue {
            return middle
        }
    }
}

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注