> For the complete documentation index, see [llms.txt](https://r24zeng.gitbook.io/leetcode-notebook/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://r24zeng.gitbook.io/leetcode-notebook/wan-quan-an-zhao-jiu-zhang-suan-fa-shua-de-60-dao-zuo-you/binary-search.md).

# I. Binary Search

\#704. Binary Search (二分查找法原型代)

Recursive is easier to write and understand;

While loop is more complicated to write, but not easy to enter dead loop, and *you'll* impresive the interviewer because most interviewees prefer recursive. 

If it's too complicated to code with while then use recursive to save time, otherwise use while.

{% hint style="info" %}

### Key point:

* start + 1 < end   （防止死循环）
* mid = start + (end-start)/2
* A\[mid] =, < , >
* A\[start]  A\[end]  ? target
  {% endhint %}

{% tabs %}
{% tab title="Java" %}

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

{% endtab %}

{% tab title="Python" %}

```python
class Soultion:
    def binarySearch(nums, target):
        start = 0
        end = len(nums)-1
        if len(nums)==0:
            return -1
            
        while start+1 < end:
            mid = start + (end-start)/2
            if nums[mid]==target:
                return mid
            elif target < nums[mid]:
                end = mid
            else:
                start = mid
        
        if nums[start]==target:
            return start
        elif nums[end]==target:
            return end
        else:
            return -1
```

> 这个方法跳出while循环后，结果是left <= target <= right 或者target < left 或者target > right，并且确保如果数组里有重复的target，一定会被至少保留一个
> {% endtab %}

{% tab title="Python-递归" %}

```python
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        # regular case
        return self.searchSub(nums, 0, len(nums)-1, target)
    
    def searchSub(self, nums, left, right, target):
        # edge case
        if left+1 >= right:
            if nums[left] == target:
                return left
            elif nums[right] == target:
                return right
            else:
                return -1

        mid = left + (right - left)//2
        if nums[mid] == target:
            return mid
        if nums[mid] > target:
            return self.searchSub(nums, left, mid, target)
        return self.searchSub(nums, mid, right, target)
```

{% endtab %}

{% tab title="Python(II)更高效" %}

```python
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left = 0
        right = len(nums) - 1
        while left <= right:
            mid = left + (right - left)//2
            if nums[mid] == target:
                return mid
            elif target > nums[mid]:
                left = mid + 1
            else:
                right = mid - 1
        return -1
```

> 这个方法只要跳出了while循环，结果是不管数组里有多少个重复的target，仅能迅速找到其中的一个，不是很通用
> {% endtab %}

{% tab title="Python(II)-递归" %}

```python
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        # regular case
        return self.searchSub(nums, 0, len(nums)-1, target)
    
    def searchSub(self, nums, left, right, target):
        # edge case
        if left > right:
            return -1

        mid = left + (right - left)//2
        if nums[mid] == target:
            return mid
        if nums[mid] > target:
            return self.searchSub(nums, left, mid-1, target)
        return self.searchSub(nums, mid+1, right, target)
                
```

{% endtab %}
{% endtabs %}

Binary search time complexity is $$O(lgN)$$ , space comlexity is $$O(lgN)$$&#x20;

### There are two common coding:

1. while loop condition: left <= right, compare with target, the stop situation is left == right + 1

```
// Some code

left = 0
right = len(nums) - 1
while left <= right:
    mid = left + (right - left) // 2
    if nums[mid] == target:
        return mid
    if nums[mid] > target:
        right = mid - 1
    else:
        left = mid + 1

return -1
```

2\. while loop condition: left < right, compare with right element, the stop condition is left == right. The example questions are: #162 PeakElement, #22 Search Rotated Array

```
// Some code

left = 0
right = len(nums) - 1
while left < right:
    mid = left + (right - left) // 2
    if nums[mid] < nums[right]
        left = mid + 1
    else:
        right = mid
return left // or return right
```