二分查找c/golang版本

之前有篇二分查找的文章，未在函数里检验参数，现以该篇文章更新，具体看代码，欢迎指正。

二分查找实例c语言版本：

#include <stdio.h>
#include <stdlib.h>

//二分查找， 以int型由小到大有序数组为例实现二分查找
int *binarySearch(int *array, int length, int aim) {
	int left, right, middle;
	int i = 0;

	//验证数组是否由小到大
	for (i = 0; i < (length - 1); i++) {
		if (array[i] > array[i + 1]) {
			printf("所传递参数数组非由小到大有序");
			exit(-1);
		}
	}

	middle = (length + 1) / 2;
	left = 0;
	right = length - 1;

	while(left <= right) {
		if (aim > array[middle]) {
			left = middle + 1;
		} else if (aim < array[middle]) {
			right = middle - 1;
		} else {
			printf("已找到目标数字%d, 要查找的数字在数组的地址是%p\n", aim, &array[middle]);
			return &array[middle];
		}

		middle = (left + right) / 2;
	}

	printf("未找到目标数字%d\n", aim);

	return NULL;
}

//测试binarySearch函数
void binarySearchTest() {
	int arr[7] = {1,2,3,4,5,6,7};//原数组
	int aimArr[3] = {2, 1, 7};//待查找目标数组
	int aim, i, *ptr = NULL;

	printf("开始测试int型有序数组二分查找， 原数组为：\n");
	for (i = 0; i < (sizeof(arr) / sizeof(int)); i ++) {
		printf("arr[%d] = %d, 地址为： %p\n", i, arr[i], &arr[i]);
	}

	for (i = 0; i < (sizeof(aimArr) / sizeof(int)); i ++) {
		aim = aimArr[i];
		printf("\n\n开始测试查找数字：%d\n", aim);
		ptr = binarySearch(arr, (sizeof(arr) / sizeof(int)), aim);
		if(NULL == ptr) {
			printf("未找到数字%d\n", aim);
		} else {
			printf("找到了数字%d, 地址为%p\n", aim, ptr);
		}
	}
	printf("\n全部测试完成\n");
}

int main() {
	binarySearchTest();

	return 0;
}

golang版本：

binarySearch.go文件如下：

package binarySearch

import (
	"log"
)

func BinarySearch(array []int, aim int) (*int, bool) {
	//验证数组是否是由小到大的顺序
	for i := 0; i < len(array)-1; i++ {
		if array[i] > array[i+1] {
			log.Println("数组非由小到大有序数组")
			return nil, false
		}
	}
	log.Println("已验证数组由小到大有序")

	//开始二分查找
	var left, right int = 0, (len(array) - 1)
	var middle int = (left + right) / 2
	for left <= right {
		if aim > array[middle] {
			left = middle + 1
		}
		if aim < array[middle] {
			right = middle - 1
		}
		if aim == array[middle] {
			log.Printf("已找到目标数 %d \n", aim)
			return &array[middle], true
		}
		middle = (left + right) / 2
	}

	//运行到此处时left > right, 表示未找到目标数
	log.Printf("没有找到目标数 %d\n", aim)

	return nil, false
}

测试文件binarySearch_test.go文件如下：

package binarySearch

import (
	"log"
	"testing"
)

func TestBinarySearch(t *testing.T) {
	array := []int{1, 2, 3, 4, 5, 6, 7} //切片
	aimArray := [...]int{3, 1, 7, 8}    //待查找数据,数组
	expextedReturn := [...]struct {
		ptr *int
		ok  bool
	}{
		{&array[2], true},
		{&array[0], true},
		{&array[6], true},
		{nil, false},
	}

	for i := 0; i < len(aimArray); i++ {
		log.Printf("开始测试查找数字 %d\n", aimArray[i])

		if ptr, ok := BinarySearch(array, aimArray[i]); expextedReturn[i].ok == ok && expextedReturn[i].ptr == ptr {
			log.Printf("测试目标数字 %d 无问题\n\n\n", aimArray[i])
		} else {
			log.Printf("测试目标数字 %d 出错了 ！！！\n\n\n", aimArray[i])
		}
	}
}

运行go test -v命令，开始单元测试，结果如下