# Binary Search

For a given sorted array (ascending order) and a target number, find the first index of this number in O(log n) time complexity.

If the target number does not exist in the array, return -1.

**Example**

If the array is **\[1, 2, 3, 3, 4, 5, 10]**, for given target **3**, return **2**.

**这是一个经典的binary serch的模板**

&#x20;**1.start+1 < end，这样就不用考虑两个指针的前后，最后结束时一定是相邻的**

**2. mid = start + (end-start/)2，虽然对python来说不重要，但是对于Java等可以防止溢出**

**3. nums\[mid] <, ==,> target 的三种情况**

**4. 是return start end的值 还是-1**

```
class Solution {
    /**
     * @param nums: The integer array.
     * @param target: Target to find.
     * @return: The first position of target. Position starts from 0.
     */
    public int binarySearch(int[] nums, int target) {
        if (nums.length == 0){
            return -1;
        }
        int start = 0;
        int end = nums.length - 1;
        int mid;
        while (start + 1 < end){
            mid = start + (end - start) / 2;
            if (target > nums[mid]){
                start = mid;
            } else if (target < nums[mid]) {
                end = mid;
            } else {
                end = mid;
            }
        }
        if (nums[start] == target){
            return start;
        } else if (nums[end] == target){
            return end;
        } else {
            return -1;
        }
    }
}
```

```
class Solution:
    # @param nums: The integer array
    # @param target: Target number to find
    # @return the first position of target in nums, position start from 0 
    def binarySearch(self, nums, target):
        if len(nums) == 0:
            return -1

        start, end = 0, len(nums) - 1
        while start + 1 < end:
            mid = (start + end) / 2
            if nums[mid] < target:
                start = mid
            else:
                end = mid

        if nums[start] == target:
            return start
        if nums[end] == target:
            return end
        return -1
```


---

# 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://rachel2011.gitbook.io/leetcode_cc150/data-structure/binary-search.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.