# General

## start < end

* \[start, end), end 為開區間
* while退出條件為 target < start = end

```java
public int binarySearch(int[] arr, int target){
    int start = 0; end = arr.length;  // [start, end)
    // target <= start = right
    while(start < end){
        int mid = start + (end - start)/2;
        if(mid > target) end = mid;
        else if (mid < target) start = mid+1;
        else return mid;
    }

    // 返回target 前一個 index
    return start;
}
```

## start + 1 < end

* while 直到 \[\[start]\[end]]相鄰退出,&#x20;
* if duplicate, 會在頭兩個的位置
* find last element of target, `if (nums[mid] == target) start = mid`

```java
public int findPosition(int[] nums, int target) {
    if (nums == null || nums.length == 0){
        return -1;
    }

    int start = 0, end = nums.length - 1;
    while (start + 1 < end){
        int mid = start + (end - start) / 2;
        if (nums[mid] == target){
            end = mid;
        }else if (nums[mid] < target){
            start = mid;
        }else{
            end = mid;
        }
    }

    if (num[start] == target){
        return start;
    }
    if (num[end] == target){
        return end;
    }
    return -1;
}
```

## 34 Find First and Last Position of Element in Sorted Array

Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.

Your algorithm's runtime complexity must be in the order of O(log n).

If the target is not found in the array, return \[-1, -1].

```java
public int[] searchRange(int[] nums, int target) {
    int[] ans = new int[2];
    if(nums == null || nums.length == 0) return new int[]{-1, -1}; 
    int start = 0, end = nums.length-1;
    while(start+1 < end){
        int mid = start + (end-start)/2;
        if(nums[mid] == target) end = mid;
        else if(nums[mid] < target) start = mid;
        else end = mid;
    }

    if(nums[start] == target) ans[0] = start;
    else if(nums[end] == target) ans[0] = end;
    else ans[0] = -1;

    start = 0;
    end = nums.length-1;
    while(start+1 < end){
        int mid = start + (end-start)/2;
        if(nums[mid] == target) start = mid;
        else if(nums[mid] < target) start = mid;
        else end = mid;
    }

    if(nums[end] == target) ans[1] = end;
    else if(nums[start] == target) ans[1] = start;
    else ans[1] = -1;

    return ans;
}
```

## 74 find element in a 2-D array

\[\[1,2,3] \[4,5,6] \[7,8,9]]

```java
end = row * column - 1
mid = (start + end) / 2
num = nums[mid/column][mid%column]
```

## 240 find element in a 2-D array ll

Find a occurrence of given number in a 2-D array

\[\[1,2,3 \[2,3,4] \[3,4,5]]

* Search from bottom left to top right
* each row is sorted, start new search y index from row + 1

```java
public int searchMatrix(int[][] matrix, int target) {
    int m = matrix.length, n = matrix[0].length;
    int x = m, y = 0;
    int count = 0;
    // search from bottom left to top right
    while (x >= 0 && y <= n){
        if (matrix[x][y] < target){
            y++;
        }else if(matrix[x][y] > target){
            x--;
        }else{
            count++;
            y++;
            x--;
        }
    }
    return count;
```

## 702 Search in a big sorted array with unknown size

Given an integer array sorted in ascending order, write a function to search target in nums. If target exists, then return its index, otherwise return -1. However, the array size is unknown to you. You may only access the array using an ArrayReader interface, where ArrayReader.get(k) returns the element of the array at index k (0-indexed).

```java
public int search(ArrayReader reader, int target) {
    int index = 1;
    while(reader.get(index-1) < target) index *=2;

    int start = index/2, end = index-1;
    while(start+1 < end){
        int mid = start + (end-start)/2;
        if(reader.get(mid) <= target) start = mid;
        else end = mid;
    }

    if(reader.get(start) == target) return start;
    if(reader.get(end) == target) return end;
    return -1;
}
```

## Search the insert position

* One more scenario to define \[1,2,3], target = 4
* Use target to define return position

```java
public int searchInsert(int[] A, int target) {
    // find first less or equal then target
    if (A == null || A.length == 0){
        return 0;
    }

    int start = 0, end = A.length -1;

    while(start+1 < end){
        int mid = start + (end-start)/2;
        if (A[mid] == target){
            start = mid;
        }else if (A[mid] < target){
            start = mid;
        }else{
            end = mid;
        }
    }

    // use target to define return position
    if (target <= A[start]){
        return start;
    }else if (target <= A[end]){
        return end;
    }else{
        return end + 1;
    }
}
```

## Count of smaller number

* Sort A first
* Not include the target number => similar to "insertion position"

```java
public List<Integer> countOfSmallerNumber(int[] A, int[] queries) {
    List<Integer> result = new ArrayList<>();

    if (queries == null || queries.length == 0){
        return result;
    }

    int lenA = A == null ? 0 : A.length;

    Arrays.sort(A);
    for (int i =0; i < queries.length; i++){
        if(lenA == 0){
            result.add(0);
        }else{
            result.add(binarySearch(A, queries[i])); 
        }
    }
    return result;
}


private int binarySearch(int[] A, int target){
    int start = 0, end = A.length -1;
    while(start + 1 < end){
        int mid = start + (end-start)/2;
        if (A[mid] == target){
            end = mid;
        }else if (A[mid] < target){
            start = mid;
        }else{
            end = mid;
        }
    }

    // not include target
    if (target <= A[start]){
        return start;
    }else if (target <= A[end]){
        return end;
    }else{
        return end + 1;
    }
}
```

## 658. Find K closest Elements

Given a sorted array, two integers `k` and `x`, find the `k` closest elements to `x` in the array.

* A\[i] to A\[i+k-1]
* Binary search, 利用 x 與兩邊的距離
* x = 3, k =2 \[1,1,2,2,2,2,2,3,3], 需特別處理 兩邊到x距離相等的情況&#x20;

```python
def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:
    l, r = 0, len(arr)-k
    while l < r:
        mid = (l+r)//2
        if arr[mid] == arr[mid+k]:
            if x > arr[mid]: l = mid+1
            else: r = mid

        elif abs(arr[mid] - x) > abs(arr[mid+k] - x):
            l = mid+1
        else:
            r = mid
    return arr[l: r+k]
```


---

# 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://netjimmy.gitbook.io/code-interview-note/binary_search/general.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.