Search order search binary search | Go subject month

A search is the process of finding a particular element from a collection of elements. The search usually returns true or false, indicating whether the element exists, respectively.

Sequential search (unordered, ordered list)

Data items stored in a collection such as a list have a linear or sequential relationship with each other, and the location of each data item is related to the other data items. In a Golang array, slice, the position of a data item is its subscript. Because the subscripts are ordered, they can be accessed sequentially, which makes sequential searches possible.

The principle of sequential search: Start with the first element in a list and follow the default order until you find the target element or run out of the list. If the target element is not found after searching the list, it is not in the list.

The sequential search Golang code for an unordered list is implemented as follows:

package main

import "fmt"

func unorderedSequentialSearch(numList []int, num int) bool {
	exist := false
	for _, value := range numList {
		if value == num {
			exist = true
			break}}return exist
}

func main(a) {
	numList := []int{2.3.1.53.23.10}
	fmt.Println(unorderedSequentialSearch(numList, 33))
	// false
	fmt.Println(unorderedSequentialSearch(numList, 1))
	// true
}
Copy the code

Assume that the elements in the list are sorted in ascending order. If there is a target element, it is still just as likely to appear in any of n positions, so the number of comparisons is the same as in an unordered list. However, if there is no target element, search efficiency is improved. If you find an element that is already larger than the target element, it means that all subsequent elements are not the target element and you can end the search prematurely without searching the entire list.

The sequential search Golang code for ordered lists is implemented as follows:

package main

import "fmt"

func orderedSequentialSearch(numList []int, num int) bool {
	exist := false
	for _, value := range numList {
		if value == num {
			exist = true
			break
		} else if value > num {
			break}}return exist
}

func main(a) {
	numList := []int{0.1.2.3.4.5.6}
	fmt.Println(unorderedSequentialSearch(numList, 33))
	// false
	fmt.Println(unorderedSequentialSearch(numList, 1))
	// true
}
Copy the code

Binary search is preferred for ordered lists

Binary search starts with the middle element. If this element is the target element, stop searching immediately; If not, use the ordered nature of the list to exclude half of the elements. If the target element is larger than the middle element, you can simply exclude the left half of the list and the middle element. This is because if the list contains the target element, it must be in the right half. Next, divide it in half for the right. Start with the middle element and compare it to the target element. Again, you can either find the target element directly, or you can cut the right half in half and narrow the search again.

Binary search Golang code for ordered lists is implemented as follows:

package main

import "fmt"

func binarySearch(numList []int, num int) bool {
	first := 0
	last := len(numList) - 1
	exist := false

	for; (first <= last) && ! (exist); { midPoint := (first + last) /2
		if numList[midPoint] == num {
			exist = true
		} else {
			if num < numList[midPoint] {
				last = midPoint - 1
			} else {
				first = midPoint + 1}}}return exist
}

func main(a) {
	numList := []int{0.1.2.3.4.5.6}
	fmt.Println(binarySearch(numList, 2))
	// true
	fmt.Println(binarySearch(numList, 9))
	// false
}

Copy the code