CodeUtility
Lập trình thông minh, làm việc hiệu quả!
Bài tập Go

Binary Search in Go

Find a value in a sorted slice by halving the search range at every step.

  • Cơ bản
  • Đọc trong 3 phút
  • 1 ví dụ chạy được
Bạn sẽ học được gì
  • low, high and middle
  • Returning -1 when missing
  • Why it is fast
Chạy code →
Search for 23
20
82
164
235
386
567
Found at index 5 after three steps.

Halve the range each step

Binary search looks at the middle of a sorted list and throws away the half that cannot contain the target. Each step halves the work, so it is very fast on large lists.

low and high mark the part that is still being searched. The function returns the position of the target, or -1 when the range becomes empty. low + (high-low)/2 finds the middle without overflow.

Những điểm quan trọng

  1. The slice must be sorted.
  2. Each step throws away half.
  3. -1 means the value is not there.

Ví dụ Go chạy được

Go
Chạy code →
main.go
package main

import "fmt"

func binarySearch(items []int, target int) int {
	low, high := 0, len(items)
	for low < high {
		middle := low + (high-low)/2
		switch {
		case items[middle] == target:
			return middle
		case items[middle] < target:
			low = middle + 1
		default:
			high = middle
		}
	}
	return -1
}

func main() {
	sorted := []int{2, 5, 8, 12, 16, 23, 38, 56}
	fmt.Println(binarySearch(sorted, 23))
	fmt.Println(binarySearch(sorted, 7))
}
Lấy nút Run cho ví dụ này Kết quả khi chạy
5
-1

Luyện tập

Mở ví dụ trong trình biên dịch online, đổi một giá trị hoặc thêm một dòng, rồi đoán kết quả trước khi chạy. Sau đó cố ý làm code bị lỗi và đọc thông báo của trình biên dịch.

Bạn học xong bài này chưa?

Đánh dấu đã học để theo dõi tiến độ của bạn.

Tiếp theo: Bank Account with Errors →

Luyện tập với thử thách

Áp dụng kiến thức của bài học này để giải một bài toán thực tế. Mỗi thử thách chạy ngay trên trình duyệt, có kiểm thử tức thì và AI nhận xét.

Tất cả thử thách