> For the complete documentation index, see [llms.txt](https://ucan.gitbook.io/notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://ucan.gitbook.io/notes/array/keys.md).

# Binary Search Template

```java
class Solution {
    public int search(int[] nums, int target) {
        // search range : [start, end)
        int start = 0;
        int end = nums.length;
        
        // remember loop condition: start < end,
        // will terminate if start == end;
        while(start<end){
            // mid position is righter (not important)
            int mid = (start+end)/2;
            if (nums[mid] == target) return mid;
            
            if(nums[mid] > target){
                // new range: [start, mid)
                end = mid;
            }
            else{
                // new range: [mid+1, end)
                start = mid+1;
            }
        }
        return -1;
    }
}
```

Divide a array (n) into two half, and the length is L

1.Start index 0, end index: L-1, middle index: L/2

If L is even, then number of elements on the left of middle: L/2 , number of elements on the right side of L: L/2-1,

If L is odd, number of elements on the left of middle point: (L-1)/2, number of elements on the right side of L: (L-1)/2

2\. start index 0, end index: L-1; middle index M = (L-1)/2&#x20;

if L is even: number of elements on the left of M: (L-1)/2, number of elements on the right side of M: (L-1)/2

if L is odd: number of elements on the left of M: (L-1)/2, number of elements on the right side of M: (L-1)/2+1;