Wonderland
Search…
2022-05-15

Description

Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.
You must write an algorithm with O(log n) runtime complexity.
Example 1:
1
Input: nums = [-1,0,3,5,9,12], target = 9
2
Output: 4
3
Explanation: 9 exists in nums and its index is 4
Copied!
Example 2:
1
Input: nums = [-1,0,3,5,9,12], target = 2
2
Output: -1
3
Explanation: 2 does not exist in nums so return -1
Copied!
Constraints:
  • 1 <= nums.length <= 10^4
  • -10^4 < nums[i], target < 10^4
  • All the integers in nums are unique.
  • nums is sorted in ascending order.

Solution

1
func search(nums []int, target int) int {
2
low := 0
3
high := len(nums) - 1
4
5
for low <= high {
6
mid := (low + high) / 2
7
if nums[mid] == target {
8
return mid
9
}
10
if nums[mid] > target {
11
high = mid - 1
12
} else {
13
low = mid + 1
14
}
15
}
16
return -1
17
}
Copied!

Description

You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.
Suppose you have n versions [1, 2, ..., n] and you want to find out the first bad one, which causes all the following ones to be bad.
You are given an API bool isBadVersion(version) which returns whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.
Example 1:
1
Input: n = 5, bad = 4
2
Output: 4
3
Explanation:
4
call isBadVersion(3) -> false
5
call isBadVersion(5) -> true
6
call isBadVersion(4) -> true
7
Then 4 is the first bad version.
Copied!
Example 2:
1
Input: n = 1, bad = 1
2
Output: 1
Copied!
Constraints:
  • 1 <= bad <= n <= 2^31 - 1

Solution

Approach #0

1
/**
2
* Forward declaration of isBadVersion API.
3
* @param version your guess about first bad version
4
* @return true if current version is bad
5
* false if current version is good
6
* func isBadVersion(version int) bool;
7
*/
8
9
func firstBadVersion(n int) int {
10
low := 1
11
high := n
12
13
for low < high {
14
mid := (low + high) / 2
15
if isBadVersion(mid) {
16
high = mid
17
continue
18
} else {
19
low = mid + 1
20
}
21
}
22
return high
23
}
Copied!

Approach #1

Using package sort:
1
/**
2
* Forward declaration of isBadVersion API.
3
* @param version your guess about first bad version
4
* @return true if current version is bad
5
* false if current version is good
6
* func isBadVersion(version int) bool;
7
*/
8
9
func firstBadVersion(n int) int {
10
return sort.Search(n, func(version int) bool { return isBadVersion(version) }
11
}
Copied!
In this problem, the giving constraints define the range of n will not over 2^31-1. However, in the real world, the value of mid may probably overflow. The official sort package shows a way to avoid overflow when computing mid with int(uint(i+j) >> 1).
Deep into the source code of Search, and we can know it also uses binary search:
1
package sort
2
3
// Search uses binary search to find and return the smallest index i
4
// in [0, n) at which f(i) is true, assuming that on the range [0, n),
5
// f(i) == true implies f(i+1) == true. That is, Search requires that
6
// f is false for some (possibly empty) prefix of the input range [0, n)
7
// and then true for the (possibly empty) remainder; Search returns
8
// the first true index. If there is no such index, Search returns n.
9
// (Note that the "not found" return value is not -1 as in, for instance,
10
// strings.Index.)
11
// Search calls f(i) only for i in the range [0, n).
12
//
13
// A common use of Search is to find the index i for a value x in
14
// a sorted, indexable data structure such as an array or slice.
15
// In this case, the argument f, typically a closure, captures the value
16
// to be searched for, and how the data structure is indexed and
17
// ordered.
18
//
19
// For instance, given a slice data sorted in ascending order,
20
// the call Search(len(data), func(i int) bool { return data[i] >= 23 })
21
// returns the smallest index i such that data[i] >= 23. If the caller
22
// wants to find whether 23 is in the slice, it must test data[i] == 23
23
// separately.
24
//
25
// Searching data sorted in descending order would use the <=
26
// operator instead of the >= operator.
27
//
28
// To complete the example above, the following code tries to find the value
29
// x in an integer slice data sorted in ascending order:
30
//
31
// x := 23
32
// i := sort.Search(len(data), func(i int) bool { return data[i] >= x })
33
// if i < len(data) && data[i] == x {
34
// // x is present at data[i]
35
// } else {
36
// // x is not present in data,
37
// // but i is the index where it would be inserted.
38
// }
39
//
40
// As a more whimsical example, this program guesses your number:
41
//
42
// func GuessingGame() {
43
// var s string
44
// fmt.Printf("Pick an integer from 0 to 100.\n")
45
// answer := sort.Search(100, func(i int) bool {
46
// fmt.Printf("Is your number <= %d? ", i)
47
// fmt.Scanf("%s", &s)
48
// return s != "" && s[0] == 'y'
49
// })
50
// fmt.Printf("Your number is %d.\n", answer)
51
// }
52
//
53
func Search(n int, f func(int) bool) int {
54
// Define f(-1) == false and f(n) == true.
55
// Invariant: f(i-1) == false, f(j) == true.
56
i, j := 0, n
57
for i < j {
58
h := int(uint(i+j) >> 1) // avoid overflow when computing h
59
// i ≤ h < j
60
if !f(h) {
61
i = h + 1 // preserves f(i-1) == false
62
} else {
63
j = h // preserves f(j) == true
64
}
65
}
66
// i == j, f(i-1) == false, and f(j) (= f(i)) == true => answer is i.
67
return i
68
}
Copied!

Description

Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
You must write an algorithm with O(log n) runtime complexity.
Example 1:
1
Input: nums = [1,3,5,6], target = 5
2
Output: 2
Copied!
Example 2:
1
Input: nums = [1,3,5,6], target = 2
2
Output: 1
Copied!
Example 3:
1
Input: nums = [1,3,5,6], target = 7
2
Output: 4
Copied!
Constraints:
  • 1 <= nums.length <= 10^4
  • -10^4 <= nums[i] <= 10^4
  • nums contains distinct values sorted in ascending order.
  • -10^4 <= target <= 10^4

Solution

1
func searchInsert(nums []int, target int) int {
2
low, high := 0, len(nums)-1
3
4
for low <= high {
5
mid := int(uint(low+high) >> 1)
6
if nums[mid] == target {
7
return mid
8
}
9
if nums[mid] > target {
10
high = mid - 1
11
} else {
12
low = mid + 1
13
}
14
}
15
return low
16
}
Copied!