Example of binary search method for Go language implementation

Use the official sort package to provide search methods to quickly implement

For the already sorted data, if you want to quickly find a certain index in the corresponding slice, we can use the search method provided by the official sort package to quickly implement binary search.

The official source code implementation is also very simple

func Search(n int, f func(int) bool) int {
  // Define f(-1) == false and f(n) == true.
  // Invariant: f(i-1) == false, f(j) == true.
  i, j := 0, n
  for i < j {
    h := int(uint(i+j) >> 1) // avoid overflow when computing h
    // i ≤ h < j
    if !f(h) {
      i = h + 1 // preserves f(i-1) == false
    } else {
      j = h // preserves f(j) == true
    }
  }
  // i == j, f(i-1) == false, and f(j) (= f(i)) == true  =>  answer is i.
  return i
}

The function is to find the minimum index of the data that meets the conditions through dichotomy, that is, the function f returns true. If the target value cannot be found, the result of parameter n is returned.

In actual business, n generally uses the length of the slice data to search, so after the Search method returns, it is necessary to determine whether i is still a reasonable index of the target slice.

Find the first index greater than or equal to x

func SearchTargetAfter(dataList []int, x int) int {
    return (len(dataList), func(i int) bool {
        return dataList[i] >= x
    })
}

Find the first index less than or equal to x

func SearchTargetBefore(dataList []int, x int) int {
    return (len(dataList), func(i int) bool {
        return dataList[i] <= x
    })
}

Find a certain number

Then I want to find a certain number. What should we do?

Give an example

arrInts := []int{1, 3, 4, 9, 12, 13}
findPos := (len(arrInts), func(i int) bool {
  return arrInts[i] == 4
})

The result output is not 2, but 6. If you look at the above source code carefully, it is not difficult to find that the official binary search method, if the numerical equality is used to judge, you must let the data fall right at the binary position each time so that you can find it. For example, in the above code, if the original slice data remains unchanged, if the search target is changed to 9, then the position can be obtained correctly.

Therefore, it should be noted here that if you want to find the target position of the determined number, when using the method, the return value of func needs to be used to find the first position greater than or equal to the target index, or the position less than or equal to the target index, and then obtain the index position, and then obtain whether the index value is the same as the target data to determine whether the data exists in this array and its location.

The above is the detailed content of the example of the binary search method to implement Go language. For more information about Go binary search, please follow my other related articles!