cpp

Проверка наличия значения в слайсе

Если слайс не отсортирован, то проверка наличия значения в слайсе сводится к перебиранию всех элементов от начала до конца. При наличии первого вхождения можно прервать поиск. Пример поиска первого вхождения приведен в листинге 5.4.

Листинг 5.4. Поиск первого вхождения элемента

package main

import "fmt"

func main() {
   arr := []int{10, 5, 6, 1, 3}
   index := search(6, arr)
   fmt.Println(index) // 2
   index = search(12, arr)
   fmt.Println(index) // -1
}
func search(key int, arr []int) int {
   for index, value := range arr {
      if value == key {
         return index
      }
   }
   return -1
}

Если значение находится в начале слайса, то поиск будет произведен достаточно быстро, но если значение расположено в конце слайса, то придется просматривать весь слайс. Если слайс состоит из 100 000 элементов, то нужно будет сделать 100 000 сравнений.

Поиск по отсортированному слайсу производится гораздо быстрее, так как не нужно каждый раз просматривать все значения слайса. Наиболее часто применяется бинарный поиск (листинг 5.5), при котором слайс делится пополам и производится сравнение значения элемента, расположенного в середине слайса, с искомым значением. Если искомое значение меньше значения элемента, то пополам делится первая половина слайса, а если больше, то пополам делится вторая половина. Далее таким же образом производится деление оставшейся части слайса. Поиск заканчивается когда будет найдено первое совпадение или когда начальный индекс станет больше конечного индекса. Таким образом, на каждой итерации отбрасывается половина оставшихся элементов. Поиск значения, которое расположено в конце слайса, состоящего из 100 000 элементов, будет произведен всего за 17 шагов. Однако, если поиск производится один раз, то затраты на сортировку сведут на нет все преимущества бинарного поиска. В этом случае прямой перебор элементов может стать эффективнее.

Листинг 5.5. Бинарный поиск в отсортированном слайсе

package main

import (
   "fmt"
   "sort"
)

func main() {
   arr := []int{10, 5, 6, 1, 3}
   // Сортируем по возрастанию
   sort.Ints(arr)
   // Производим поиск
   index := bsearch(6, arr)
   fmt.Println(index) // 3
   index = bsearch(12, arr)
   fmt.Println(index) // -1
}
// Бинарный поиск в отсортированном массиве
func bsearch(key int, arr []int) int {
   if len(arr) < 1 {
      return -1
   }
   start := 0
   end := len(arr) - 1
   i := 0
   for start <= end {
      i = (start + end) / 2
      if arr[i] == key {
         return i
      } else if arr[i] < key {
         start = i + 1
      } else if arr[i] > key {
         end = i - 1
      }
   }
   return -1
}

Для поиска элемента внутри отсортированного слайса можно воспользоваться следующими стандартными функциями из пакета sort:

  • SearchInts() — производит поиск элемента x внутри слайса a. Возвращает позицию вставки элемента в отсортированный слайс. Обратите внимание: чтобы убедиться в наличии элемента нужно выполнить дополнительную проверку. Формат функции:
sort.SearchInts(a []int, x int) int

Пример:

arr := []int{10, 5, 6, 1, 3}
// Сортируем по возрастанию
sort.Ints(arr)
fmt.Println(arr)                   // [1 3 5 6 10]
// Производим поиск
key := 3
index := sort.SearchInts(arr, key) // Есть элемент
fmt.Println(index)                 // 1
// Проверяем найден ли элемент
if index < len(arr) && arr[index] == key {
   fmt.Println("Элемент найден. Индекс", index)
} else {
   fmt.Println("Элемент не найден")
}
index = sort.SearchInts(arr, 2)  // Нет элемента
fmt.Println(index)               // 1 (место вставки)
index = sort.SearchInts(arr, 11) // Нет элемента
fmt.Println(index)               // 5 (len(arr))
  • SearchFloat64s() — производит поиск элемента x внутри слайса a. Возвращает позицию вставки элемента в отсортированный слайс. Обратите внимание: чтобы убедиться в наличии элемента нужно выполнить дополнительную проверку. Формат функции:
sort.SearchFloat64s(a []float64, x float64) int

Пример:

arr := []float64{5.5, 6.3, 1.4, 10.5, 3.3}
// Сортируем по возрастанию
sort.Float64s(arr)
fmt.Println(arr)                       // [1.4 3.3 5.5 6.3 10.5]
// Производим поиск
key := 3.3
index := sort.SearchFloat64s(arr, key) // Есть элемент
fmt.Println(index)                     // 1
// Проверяем найден ли элемент
if index < len(arr) && arr[index] == key {
   fmt.Println("Элемент найден. Индекс", index)
} else {
   fmt.Println("Элемент не найден")
}
index = sort.SearchFloat64s(arr, 2.3)  // Нет элемента
fmt.Println(index)                     // 1 (место вставки)
index = sort.SearchFloat64s(arr, 11.5) // Нет элемента
fmt.Println(index)                     // 5 (len(arr))
  • SearchStrings() — производит поиск элемента x внутри слайса a. Возвращает позицию вставки элемента в отсортированный слайс. Обратите внимание: чтобы убедиться в наличии элемента нужно выполнить дополнительную проверку. Формат функции:
sort.SearchStrings(a []string, x string) int

Пример:

arr := []string{"d", "a", "e", "b"}
// Сортируем по возрастанию
sort.Strings(arr)
fmt.Println(arr)                      // [a b d e]
// Производим поиск
key := "b"
index := sort.SearchStrings(arr, key) // Есть элемент
fmt.Println(index)                    // 1
// Проверяем найден ли элемент
if index < len(arr) && arr[index] == key {
    fmt.Println("Элемент найден. Индекс", index)
} else {
   fmt.Println("Элемент не найден")
}
index = sort.SearchStrings(arr, "c") // Нет элемента
fmt.Println(index)                   // 2 (место вставки)
index = sort.SearchStrings(arr, "f") // Нет элемента
fmt.Println(index)                   // 4 (len(arr))
  • Search() — производит поиск элемента внутри слайса. В первом параметре функция принимает число элементов слайса, а во втором — функцию сравнения. Возвращает позицию вставки элемента в отсортированный слайс. Обратите внимание: чтобы убедиться в наличии элемента нужно выполнить дополнительную проверку. Формат функции:
sort.Search(n int, f func(int) bool) int

Пример:

arr := []int{10, 5, 6, 1, 3}
// Сортируем по возрастанию
sort.Ints(arr)
fmt.Println(arr)   // [1 3 5 6 10]
// Производим поиск
key := 3
index := sort.Search(len(arr), func(i int) bool {
   return arr[i] >= key
})                 // Есть элемент
fmt.Println(index) // 1
// Проверяем найден ли элемент
if index < len(arr) && arr[index] == key {
   fmt.Println("Элемент найден. Индекс", index)
} else {
   fmt.Println("Элемент не найден")
}
index = sort.Search(len(arr), func(i int) bool {
   return arr[i] >= 2
})                 // Нет элемента
fmt.Println(index) // 1 (место вставки)
index = sort.Search(len(arr), func(i int) bool {
   return arr[i] >= 11
})                 // Нет элемента
fmt.Println(index) // 5 (len(arr))

Учебник Go (Golang)
Учебник Go (Golang) в формате PDF

Помощь сайту

ЮMoney (Yandex-деньги): 410011140483022

ПАО Сбербанк:
Счет: 40817810855006152256
Реквизиты банка:
Наименование: СЕВЕРО-ЗАПАДНЫЙ БАНК ПАО СБЕРБАНК
Корреспондентский счет: 30101810500000000653
БИК: 044030653
КПП: 784243001
ОКПО: 09171401
ОКОНХ: 96130
Скриншот реквизитов

cpp