2.11 Tìm kiếm nhị phân (Binary Search)

• Cách viết kinh điển của tìm kiếm nhị phân. Cần chú ý 3 điểm:
  1. Điều kiện thoát vòng lặp: chú ý là low <= high, không phải low < high.
  2. Cách tính mid: mid := low + (high-low)>>1
  3. Cách cập nhật low và high: low = mid + 1, high = mid - 1.

func binarySearchMatrix(nums []int, target int) int {
	low, high := 0, len(nums)-1
	for low <= high {
		mid := low + (high-low)>>1
		if nums[mid] == target {
			return mid
		} else if nums[mid] > target {
			high = mid - 1
		} else {
			low = mid + 1
		}
	}
	return -1
}

• Biến thể của tìm kiếm nhị phân. Có 4 biến thể cơ bản:
  1. Tìm phần tử đầu tiên bằng target, độ phức tạp $O(log n)$
  2. Tìm phần tử cuối cùng bằng target, độ phức tạp $O(log n)$
  3. Tìm phần tử đầu tiên lớn hơn hoặc bằng target, độ phức tạp $O(log n)$
  4. Tìm phần tử cuối cùng nhỏ hơn hoặc bằng target, độ phức tạp $O(log n)$

// Tìm kiếm nhị phân phần tử đầu tiên bằng target, độ phức tạp O(logn)
func searchFirstEqualElement(nums []int, target int) int {
	low, high := 0, len(nums)-1
	for low <= high {
		mid := low + ((high - low) >> 1)
		if nums[mid] > target {
			high = mid - 1
		} else if nums[mid] < target {
			low = mid + 1
		} else {
			if (mid == 0) || (nums[mid-1] != target) { // Tìm phần tử đầu tiên bằng target
				return mid
			}
			high = mid - 1
		}
	}
	return -1
}

// Tìm kiếm nhị phân phần tử cuối cùng bằng target, độ phức tạp O(logn)
func searchLastEqualElement(nums []int, target int) int {
	low, high := 0, len(nums)-1
	for low <= high {
		mid := low + ((high - low) >> 1)
		if nums[mid] > target {
			high = mid - 1
		} else if nums[mid] < target {
			low = mid + 1
		} else {
			if (mid == len(nums)-1) || (nums[mid+1] != target) { // Tìm phần tử cuối cùng bằng target
				return mid
			}
			low = mid + 1
		}
	}
	return -1
}

// Tìm kiếm nhị phân phần tử đầu tiên >= target, độ phức tạp O(logn)
func searchFirstGreaterElement(nums []int, target int) int {
	low, high := 0, len(nums)-1
	for low <= high {
		mid := low + ((high - low) >> 1)
		if nums[mid] >= target {
			if (mid == 0) || (nums[mid-1] < target) { // Tìm phần tử đầu tiên >= target
				return mid
			}
			high = mid - 1
		} else {
			low = mid + 1
		}
	}
	return -1
}

// Tìm kiếm nhị phân phần tử cuối cùng <= target, độ phức tạp O(logn)
func searchLastLessElement(nums []int, target int) int {
	low, high := 0, len(nums)-1
	for low <= high {
		mid := low + ((high - low) >> 1)
		if nums[mid] <= target {
			if (mid == len(nums)-1) || (nums[mid+1] > target) { // Tìm phần tử cuối cùng <= target
				return mid
			}
			low = mid + 1
		} else {
			high = mid - 1
		}
	}
	return -1
}

• Dùng tìm kiếm nhị phân trong mảng “gần như có thứ tự”. Có thể giải bằng cách kinh điển hoặc các biến thể. Dạng bài hay gặp: tìm đỉnh trong mảng núi, tìm điểm phân chia trong mảng đã sắp xếp bị xoay. Bài 33, 81, 153, 154, 162, 852.

func peakIndexInMountainArray(A []int) int {
	low, high := 0, len(A)-1
	for low < high {
		mid := low + (high-low)>>1
		// Nếu A[mid] > A[mid+1] thì đỉnh nằm bên trái (kể cả mid) => high = mid
		// Ngược lại đỉnh nằm bên phải => low = mid + 1
		if A[mid] > A[mid+1] {
			high = mid
		} else {
			low = mid + 1
		}
	}
	return low
}

• Dạng bài “tối thiểu hóa giá trị lớn nhất” (max-min). Tìm giá trị lớn nhất nhỏ nhất sao cho thỏa điều kiện. Bài 410, 875, 1011, 1283.

---