# 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)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://timmybeeflin.gitbook.io/cracking-leetcode/binary-search/template.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.