Go 实现二分查找算法

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

声明：本文内容由网友自发贡献，本站不承担相应法律责任。对本内容有异议或投诉，请联系2913721942#qq.com核实处理，我们将尽快回复您，谢谢合作！