二分查找

在计算机科学中，二分搜索（binary search），也称折半搜索（half-interval search）、对数搜索（logarithmic search），是一种在有序数组中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。

算法源码 这里，我主要采用递归和非递归两种方法实现，具体如下：

首先第一种是非递归的算法实现，算法如下：

Go

package main

import "fmt"

func main() {
   var arr = []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
   offset := binarySearch(arr, 9)
   fmt.Println(offset)
}

// 二分查找
func binarySearch(arr []int, number int) int {
   if len(arr) == 0 {
      return -1
   }

   lower := 0
   high := len(arr) - 1
   for lower <= high {
      // 以中间点作为参照点比较
      middle := (high + lower) / 2
      if arr[middle] > number {
         // 查找数比参照点小，舍去右边
         high = middle - 1
      } else if arr[middle] < number {
         // 查找数比参照点大，舍去左边
         lower = middle + 1
      } else {
         return middle
      }
   }
   // 未找到，返回-1
   return -1
}

// 递归版
func recursion(arr []int, number, lower, high int) int {
	middle := (lower + high) / 2
	if lower > high {
		return -1
	}
	if arr[middle] > number {
		return recursion(arr, number, lower, middle-1)
	} else if arr[middle] < number {
		return recursion(arr, number, middle+1, high)
	} else {
		return middle
	}
}

PHP