> For the complete documentation index, see [llms.txt](https://netjimmy.gitbook.io/code-interview-note/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://netjimmy.gitbook.io/code-interview-note/binary_search/general.md).

# 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]
```