codekofi
← All questions

Binary Search

HardBinary Search

The problem

Given an array sorted in increasing order and a target value, return the index where the target sits, or -1 if it is not there.

The search must be logarithmic in the length of the array.

search({-1, 0, 3, 5, 9, 12}, 9)

One of these three is correct

Two lines apart, at the closest.

The wrong ones are this same code with between two and five lines changed. Some of those changes do not compile. There is no Run button: running all three would turn this into a vote rather than a reading.

1int search(const vector<int>& nums, int target) {
2
3 int n = nums.size();
4 int lo = 1;
5 int hi = n - 1;
6
7 while (lo < hi) {
8
9 int mid = lo + (hi - lo) / 2;
10
11 if (nums[mid] == target) {
12 return mid;
13 }
14
15 if (nums[mid] < target) {
16 lo = mid + 1;
17 } else {
18 hi = mid - 1;
19 }
20 }
21
22 return -1;
23}
1int search(const vector<int>& nums, int target) {
2
3 int n = nums.size();
4 int lo = 0;
5 int hi = n - 1;
6
7 while (lo <= hi) {
8
9 int mid = lo + (hi - lo) / 2;
10
11 if (nums[mid] == target) {
12 return mid;
13 }
14
15 if (nums[mid] < target) {
16 lo = mid + 1;
17 } else {
18 hi = mid - 1;
19 }
20 }
21
22 return -1;
23}
1int search(const vector<int>& nums, int target) {
2
3 int n = nums.size();
4 int lo = 1;
5 int hi = n - 1;
6
7 while (lo <= hi) {
8
9 int mid = lo + (hi - lo) / 2;
10
11 if (nums[mid - 1] == target) {
12 return mid;
13 }
14
15 if (nums[mid] < target) {
16 lo = mid + 1;
17 } else {
18 hi = mid - 1;
19 }
20 }
21
22 return -1;
23}