二分查找

Java 版本

public class BinarySearch {

    public static void main(String[] args) {

        int[] arr = {0, 0, 10, 11, 134, 1111, 1112,  19820};
        int target1 = 0;
        int target2 = -1;
        int target3 = 1111;

        System.out.println(binarySearch(arr, target1));
        System.out.println(binarySearch(arr, target2));
        System.out.println(binarySearch(arr, target3));
    }


    /**
     * 二分搜索，搜不到返回 -1
     * @param arr 有序数组
     * @return target 所在 arr 的索引
     */
    public static int binarySearch (int[] arr, int target) {
        return help(arr, target,0, arr.length -1);
    }

    public static int help(int[] arr, int target, int left, int right){
        if (right < left) {
            return -1;
        }
        int mid = right - (right - left) / 2;
        if (arr[mid] == target ) {
            return mid;
        } else if (arr[mid] < target) {
            return help(arr, target, mid + 1, right);
        } else {
            return help(arr, target, left, mid - 1);
        }
    }
}

Go 版本

package main

import "fmt"

func main() {
	arr := []int{1, 2, 3, 4, 5, 10, 20, 30}
	target := []int{0, 1, 5, 30, 31}
	for _, t := range target {
		fmt.Printf("target [%d] is at the index of [%d] in arr.\n", t, binarySearch(arr, t))
	}
}

// 二分查找
// arr 必须有序
func binarySearch(arr []int, target int) int {
	return help(arr, 0, len(arr)-1, target)
}

func help(arr []int, left, right, target int) int {
	if right < left {
		return -1
	}
	midIndex := (right-left)/2 + left
	if arr[midIndex] == target {
		// 相等即找到，返回
		return midIndex
	} else if arr[midIndex] < target {
		// 中间值比目标值小，则往右边找
		return help(arr, midIndex+1, right, target)
	} else {
		// 中间值比目标值打，则往左边找
		return help(arr, left, midIndex-1, target)
	}
}

输出：

target [0] is at the index of [-1] in arr.
target [1] is at the index of [0] in arr.
target [5] is at the index of [4] in arr.
target [30] is at the index of [7] in arr.
target [31] is at the index of [-1] in arr.