> For the complete documentation index, see [llms.txt](https://timmybeeflin.gitbook.io/cracking-leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://timmybeeflin.gitbook.io/cracking-leetcode/binary-search/template.md).

# Template & Tips

binary search 概念是, 要找左半部還是右半部？

三分法 use left <= left

二分法 use left < left

## 1. 找模糊值 first or last occurrence, 二分法

see leetcode 34

```java
        int left = 0;
        int right = nums.length - 1;
        // find first occurrence
        while (left < right) {
            int mid = left + (right - left)/2;

            if (nums[mid] < target) { // 往右半部找
                left = mid + 1;
            } else { // 往左半部找
                right = mid;
            }
        }
        return left; // right
        
        // find last occurrence
        while (left  < right) {
            int mid = left + (right - left + 1)/2; // notice! +1

            if (nums[mid] > target) { // 往左半部找
                right = mid - 1;
            } else { // 往右半部找
                left = mid;
            }
        }
        return left;
```

## 2. 找確切值, 三分法, template,&#x20;

```
left, right = 0, len(array) - 1 
while left <= right: 
    // (left + right) >>> 1 is best!
	  mid = (left + right) >>> 1    // left + (right - left) / 2 
	  if array[mid] == target: 
		    # find the target!! 
		    break or return result 
	  elif array[mid] < target: 
		    left = mid + 1 
	  else: 
		    right = mid - 1
```

1. when do you use while (start < end) , when do you use while (start <= end) ?

You use `while (start <= end)` if you are returning the match from inside the loop.

You use `while (start < end)` if you want to exit out of the loop first, and then use the result of `start` or `end` to return the match.

可以參考這篇的思路：

<https://leetcode-cn.com/problems/search-insert-position/solution/te-bie-hao-yong-de-er-fen-cha-fa-fa-mo-ban-python-/>

## 3. 找最近似值 (closet to ...)

```java
        int left = 0;
        int right = nums.length - 1;
        // find first occurrence
        while (left + 1 < right) {
            int mid = (left + right) >>> 1; 

            if (nums[mid] < target) { // 往右半部找
                left = mid;
            } else { // 往左半部找
                right = mid;
            }
        }
        if (nums[right] < target) { // right < target , target 最大 
            return right;
        } else if (nums[left] > target) { //  target  < left  , target 最小
            return left;
        } else { // left < target < right ,  target 介於中間
            return (target - nums[left] < nums[right] - target) ? left : right;
        }
        

```

## find peak (162)

```java
if (nums[mid] < nums[mid+1]) {
    left = mid + 1;
} else {
    right = mid;
}
```

## Rotated

```java
            while (left <= right) ...
            
            // duplicate 多這個條件
            if (nums[start] == nums[mid] && nums[mid] == nums[end]) {
                start++;
                end--;
            } else if (nums[start] <= nums[mid]) {
                if (nums[start] <= target && target <= nums[mid]) { // in left
                    end = mid - 1;
                } else {
                    start = mid + 1;
                }
                    
            } else {
                if (nums[mid] <= target && target <= nums[end]) {
                    start = mid + 1;
                } else {
                    end = mid - 1;
                }
            }
```

## Mini in Rotated

```java
if (nums[mid] > nums[right]) {
    left = mid + 1;
} else {
    right = mid;
}

// duplicate
if (nums[mid] > nums[right]) {
    left = mid + 1;
} else if (nums[mid] < nums[right]) {
    right = mid;
} else { // nums[mid] == nums[right] .=> add this 
    right--;
}
```

## 二分法

### 二分查找 tips

### decrease and conquer template

![](https://i.imgur.com/ePZoW2b.png)

原始 binary search 寫法分成三部分&#x20;

![](https://i.imgur.com/J3N2IIu.png)

### 另一種做法

### decrease and conquer, 朝排除 mid 思考, 分為兩部份&#x20;

![](https://i.imgur.com/GHnIvMk.png)

while(left < right) 這樣寫退出時, **left == right, 所以回 left or right 都可以**&#x20;

![](https://i.imgur.com/SYXwjXw.png)

根據邊界收縮,中間值要考慮 只有兩個元素時, \[0, 1] => mid = (0+1)/2 = 0, 永遠取不到右中位數  &#x20;

![](https://i.imgur.com/4YBQNgW.png)

上取整可以解決&#x20;

![](https://i.imgur.com/d2EkpM4.png)

![](https://i.imgur.com/4W1Ww1z.png)

如果題目說搜索區間必定有 target, 就ok 但如果可能是會找不到的, 就不是一定要回傳 nums\[left], nums\[right] ![](https://i.imgur.com/B8rkAHG.png)

根據什麼時候狀況不是解, 寫if, if對 else 自然對

&#x20;&#x20;

![](https://i.imgur.com/mjJQFpt.png)

![](https://i.imgur.com/YT0qppW.png)

![](https://i.imgur.com/alm9RNK.png)

第二解, 因為可以插入在最後, 所以可以不用特別判斷, 所以 右邊界 可以改成 len&#x20;

![](https://i.imgur.com/P58oM0c.png)

第三解, 因為看到目標元素, 就達成題目要的, 所以可以多一個 == 的挑件判斷直接返回答案&#x20;

![](https://i.imgur.com/OO72bp4.png)