提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  后端

当前栏目

Go 实现二分查找算法

Go算法 实现 查找 二分
2023-06-13 09:18:39 时间

Go 实现二分查找算法

二分查找算法简介：二分查找算法对有序数组有效，二分搜索是查找数组中的目标值。

在一个有序数组中，将数组分成两段，将要查询的铁元素和分割点比较：

  1. 如果相等，直接返回，说明数据找到
  2. 目标元素大于分割点，在分割点右边继续查找
  3. 元素小于分割点，在分割点左侧继续查找

二分查找算法模板：

int binarySearch(int[] nums, int target) {
    int left = 0, right = ...;

    while(...) {
        int mid = (right + left) / 2;
        if (nums[mid] == target) {
            ...
        } else if (nums[mid] < target) {
            left = ...
        } else if (nums[mid] > target) {
            right = ...
        }
    }
    return ...;
}

再有个标准写法

int BinarySearch(int array[], int n, int value)
{
    int left = 0;
    int right = n - 1;
    //如果这里是int right = n 的话，那么下面有两处地方需要修改，以保证一一对应：
    //1、下面循环的条件则是while(left < right)
    //2、循环内当 array[middle] > value 的时候，right = mid

    while (left <= right)  //循环条件，适时而变
    {
        int middle = left + ((right - left) >> 1);  //防止溢出，移位也更高效。同时，每次循环都需要更新。

        if (array[middle] > value)
        {
            right = middle - 1;  //right赋值，适时而变
        }
        else if(array[middle] < value)
        {
            left = middle + 1;
        }
        else
            return middle;
        //可能会有读者认为刚开始时就要判断相等，但毕竟数组中不相等的情况更多
        //如果每次循环都判断一下是否相等，将耗费时间
    }
    return -1;
}

Go-二分查找算法

给定一个有序数组，查找第一个等于 target 的下标，找不到返回 -1.

代码中有一个要注意的是溢出问题： mid := low + ((high - low) >> 1) // 溢出

代码实现如下:

package algorithm

import (
	"fmt"
	"testing"
)

func binarySearch(arr []int, target int) int {
	low := 0
	high := len(arr) - 1
	for low <= high {
		//mid := (low + high) / 2
		mid := low + ((high - low) >> 1)
		//fmt.Println(mid)
		if arr[mid] > target {
			high = mid - 1
		} else if arr[mid] < target {
			low = mid + 1
		} else {
			return mid
		}
	}
	return -1
}

func TestBinarySearch(t *testing.T) {
	/*arr := make([]int, 1024*1024, 1024*1024)
	for i := 0; i < 1024*1024; i++ {
		arr[i] = i + 1
	}*/

	//arr := []int{1, 9, 10, 30, 2, 5, 45, 8, 63, 234, 12}
	//QuickSort(arr, 0, len(arr)-1)
	//fmt.Println(arr)
	arr := []int{1, 2, 5, 8, 9, 10, 12, 30, 45, 63, 234}

	id := binarySearch(arr, 9)
	if id != -1 {
		fmt.Println(id, arr[id])
	} else {
		fmt.Println("没有找到数据")
	}
}

执行结果如下：

=== RUN   TestBinarySearch
3 8
--- PASS: TestBinarySearch (0.00s)
PASS

相关文章