Golang查找-顺序查找-二分法查找方法思路详解

package main

import (
	"fmt"
)

//顺序查找就是在一个序列中一个一个数进行对比指导找到查找的值
//顺序查找方法一
func Orderfindvalue(arrslice []int, findvalue int) {
	for i := 0; i < len(arrslice); i++ {
		if findvalue == arrslice[i] {
			fmt.Printf("找到了,下标是%v
", i)
			//找到以后我们结束循环
			break
		} else if i == len(arrslice)-1 { //这里为什么用下标和最后一个数进行比较，就是当查找到最后一个数 如果也没有找到就返回没有找到
			fmt.Printf("没有找到")
		}
	}
}

//顺序查找方法二
func Orderfindvalue1(arrslice []int, findvalue int) {
	//首先我们定义一个index变量 代表索引下标
	//如果index 是-1 就是没有找到，这样的话,逻辑会跟清楚,相当一个标志位，代码的可读性也提高了不少
	index := -1
	for i, value := range arrslice {
		if value == findvalue {
			index = i
			break
		}
	}
	//来判断有没有找到
	if index != -1 {
		fmt.Printf("找到了,下标是%v
", index)
	} else {
		fmt.Printf("没有找到")
	}
}

//二分法查找 思路分析变成代码
//注意事项,二分法查找必须是在有序序列中查找
/*
二分法查找的思路:比如我们要查找的数是 findvalue (变量名)  // 声明变量 findvalue=8
1. arrslice 必须是一个有序序列，并且是从小到大排序        // 声明变量 arrslice=[]int{1,3,7,9,10,11,15}
2.先找到 中间数组的下标 middle=(leftindex + rightindex)/2 求出我们中间索引的位置，然后让数组中间下标的值和findvalue进行比较，会有以下几种可能
2.1 如果arrslice[middle] > findvalue ,就应该向 leftindex---(middle - 1) 中查找
2.2 如果arrslice[middle] < findvalue ,就应该向 (middle + 1 ) --- rightindex 中查找
2.3 如果  arrslice[middle] == findvalue ,就说明找到了
2.4 上面的 2.1 、 2.2 、2.3 的逻辑会递归执行
3. 想一下,在上面情况下，就说明找不到( 分析出退出递归的条件 ) 凡是涉及到递归，都要考虑退出递归不然就死归了
   if leftindex > rigthindex {
	   //找不到
	   return
   }
*/
var count int = 0

func BinaryFind(arrslice []int, leftindex int, rigthindex int, findvalue int) {

	if leftindex > rigthindex {
		fmt.Printf("没有找到
")
		return
	}
	middle := (leftindex + rigthindex) / 2
	//如果中间索引的值大于我们找的值 就应该向 leftindex---(middle - 1) 中查找
	if arrslice[middle] > findvalue {
		BinaryFind(arrslice, leftindex, (middle - 1), findvalue)
		count++
	} else if arrslice[middle] < findvalue {
		BinaryFind(arrslice, (middle + 1), rigthindex, findvalue)
		count++
	} else {
		fmt.Printf("找到了 下标是%v
", middle)
		count++
	}

}

func main() {
	//无序序列 也就是一个切片或者数组(切片底层实际上也是数组)
	// arrslice := []int{1, 7, 2, 8, 9, 3}

	//顺序查找方法一
	// Orderfindvalue(arrslice, 9)

	//顺序查找方法二 (推荐方法)
	// Orderfindvalue1(arrslice, 10)

	//二分法查找 
        //申明有序序列
	arrslice := []int{1, 3, 7, 9, 10, 11, 15}
	BinaryFind(arrslice, 0, len(arrslice)-1, 9)
	fmt.Printf("count:%v
", count)
}