0%

# 选择

`l = mid + 1` `l = mid` `r = mid - 1` `r = mid`

`vec[mid] >= target` `vec[mid] <= target`

## 边界

1. `while (l <= r); l = mid + 1; r = mid - 1;`
2. `while (l < r); l = mid + 1; r = mid - 1;`
3. `while (l < r); l = mid + 1; r = mid;`
4. `while (l < r - 1); l = mid; r = mid;`

• `l <= r` 时， `r = mid - 1`是合法的，`r = mid`会陷入死循环

`l = 3``r = 3`时陷入死循环

• `l < r`时， `r = mid`是合法的。 `l = mid`会陷入死循环

`l = 3``r = 3`时陷入死循环

## 总结

### 在sorted数组中，返回第一个不小于target的元素的index

1. `vec[mid] == target` -> `r = mid`
2. `vec[mid] < target` -> `l = mid + 1`
3. `vec[mid] > target` -> `r = mid - 1`

### 在sorted数组中，返回第一个大于target的元素的index

1. `vec[mid] == target` -> `l = mid + 1`
2. `vec[mid] < target` -> `l = mid + 1`
3. `vec[mid] > target` -> `r = mid`

### 在sorted数组中，返回第一个target元素的index

1. `vec[mid] == target` -> `r = mid`
2. `vec[mid] > target` -> `r = mid - 1`
3. `vec[mid] < target` -> `l = mid + 1`

### 在sorted数组中，返回最后一个target元素的index

1. `vec[mid] == target` -> `l = mid`
2. `vec[mid] > target` -> `r = mid - 1`
3. `vec[mid] < target` -> `l = mid + 1`

## Binary Search in Rotated Array

I met this question in an interview.
Well, you can definitely find a more elegent solution than this one.
The thought is simple, find the indent first. Then, you can transfer this question into typical binary search.