题目一

给定一个旋转的有序数组，比如{7,8,9,10,1,2,3} // 是{1,2,3,7,8,9,10}旋转之后得到的， // 在数组中查找是否存在元素key。假定数组中不存在重复元素。 golang进行实现

实现

js
package main


import "fmt"

func search(nums []int, key int) bool {
	left, right := 0, len(nums)-1

	for left <= right {
		mid := left + (right-left)/2

		if nums[mid] == key {
			return true
		}

		// 左半部分有序
		if nums[left] <= nums[mid] {
			if nums[left] <= key && key < nums[mid] {
				right = mid - 1
			} else {
				left = mid + 1
			}
		} else {
			// 右半部分有序
			if nums[mid] < key && key <= nums[right] {
				left = mid + 1
			} else {
				right = mid - 1
			}
		}
	}
	return false
}

func main() {
	nums := []int{7, 8, 9, 10, 1, 2, 3}

	fmt.Println(search(nums, 1))  // true
	fmt.Println(search(nums, 8))  // true
	fmt.Println(search(nums, 5))  // false
}

将二维数组看做一维数组的技巧

js
row = idx / n
col = idx % n

题目二

该题的重点就是知道如何把二维数组当做一维数组进行处理，然后进行二分查找

给你一个满足下述两条属性的 m x n 整数矩阵：每行中的整数从左到右按非严格递增顺序排列。每行的第一个整数大于前一行的最后一个整数。给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。

js
func searchMatrix(matrix [][]int, target int) bool {
	if len(matrix) == 0 || len(matrix[0]) == 0 {
		return false
	}

	m, n := len(matrix), len(matrix[0])
	left, right := 0, m*n-1

	for left <= right {
		mid := left + (right-left)/2
		row := mid / n
		col := mid % n

		if matrix[row][col] == target {
			return true
		} else if matrix[row][col] < target {
			left = mid + 1
		} else {
			right = mid - 1
		}
	}
	return false
}

目录

题目一

实现

将二维数组看做一维数组的技巧

题目二