二分查找

二分查找

等于目标元素的索引

func getTarget(nums []int, target int) int {
	left := 0
	right := len(nums) - 1
	for left <= right {
		mid := left + (right-left)>>2
		if nums[mid] == target {
			return mid
		} else if nums[mid] > target {
			right = mid - 1
		} else {
			left = mid + 1
		}
	}
	return -1
}

第一个大于等于目标元素的索引

func getFirstTarget(nums []int, target int) int {
	left := 0
	right := len(nums) - 1
	for left <= right {
		mid := left + (right-left)>>2
		if nums[mid] >= target {
			right = mid - 1
		} else {
			left = mid + 1
		}
	}
	return left
}

最后一个小于等于目标元素的索引

func getLastTarget(nums []int, target int) int {
	left := 0
	right := len(nums) - 1
	for left <= right {
		mid := left + (right-left)>>2
		if nums[mid] <= target {
      left = mid + 1
		} else {
			right = mid - 1
		}
	}
	return right
}

第一个大于目标元素的索引

func getFirstLargerTarget(nums []int, target int) int {
	left := 0
	right := len(nums) - 1
	for left <= right {
		mid := left + (right-left)>>2
		if nums[mid] > target {
			if mid == 0 || nums[mid-1] <= target {
				// mid == 0 所有值都比target大
				// nums[mid-1] <= target 说明mid是第一个比目标值大的索引
				return mid
			} else {
				right = mid - 1
			}
		} else if nums[mid] <= target {
			left = mid + 1
		}
	}
	//所有元素都小于目标元素
	return -1
}

最后一个小于目标元素的索引

func getLastSmall(nums []int, target int) int {
	left := 0
	right := len(nums) - 1
	for left <= right {
		mid := left + (right-left)>>2
		if nums[mid] >= target {
			right = mid - 1
		} else nums[mid] < target {
			if mid == len(nums)-1 || nums[mid+1] >= target {
				// mid == len(nums)-1 所有元素都小于目标元素
				// nums[mid+1] >= target mid是最后一个小于目标元素的索引
				return mid
			}
			left = mid + 1
		}
	}
	//所有元素都大于目标元素
	return -1
}

在旋转有序数组中找目标元素的索引

// [5,6,7,1,2,3]
func getTargetInLoop(nums []int, target int) int {
	left := 0
	right := len(nums) - 1

	for left <= right {
		mid := left + (right-left)>>1
		if nums[mid] == target {
			return mid
		}
		if nums[left] <= nums[mid] { // left和right相差1时，mid=left
			// 说明 left和mid在同一个有序数组里
			if target >= nums[left] && target < nums[mid] {
				// 说明 target 在 left和mid中间 需要移动right
				right = mid - 1
			}else {
				// target 和 (left/mid)不在同一个有序数组
				left = mid + 1
			}
		} else {
			// 说明 mid和right在同一个有序数组里
			if nums[mid] < target && nums[right] >= target {
				// 说明 target 在mid和right中间 需要移动left
				left = mid + 1
			}else{
				// target 和 (mid/right)不在同一个有序数组
				right = mid - 1
			}
		}
	}
	return -1
}

二维数组中查找目标元素的索引

func getTargetInTwoDimensional(nums [][]int, target int) bool {
	line := len(nums)
  if line == 0 {
    return false
  }
	col := len(nums[0])

	left := 0
	right := line*col - 1
	for left <= right {
		mid := left + (right-left)>>2
		x := mid / col
		y := mid % col
		if nums[x][y] == target {
			return true
		} else if nums[x][y] > target {
			right = mid - 1
		} else {
			left = mid + 1
		}
	}
	return false
}