# 704. Binary Search
[](https://hackmd.io/eJevxVSAScaBKzmGOFJgdA)

###### tags: `Leetcode`

Author: @ElocinZhan

Source: [:link:][leetcode link]

[leetcode link]:
https://leetcode.com/problems/binary-search/

Average Rating：:star::star::star::star::star:

## Question Description

:::info
Given an array of integers `nums` which is sorted in ascending order, and an integer `target`, write a function to search `target` in `nums`. If `target` exists, then return its `index`. Otherwise, return `-1`.

You must write an algorithm with O(log n) runtime complexity.
:::

**Example 1**

Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Explanation: 9 exists in nums and its index is 4

**Example 2**

Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1
Explanation: 2 does not exist in nums so return -1

**Constraints:**

1 <= nums.length <= 10^4
-10^4 < nums[i], target < 10^4
All the integers in nums are unique.
nums is sorted in ascending order.

## Question Explanation

***English Version***

==Binary search== is a textbook algorithm based on the idea to compare the target value to the middle element of the array

+ If the target value is equal to the middle element, we are done
+ if the target value is smaller than the middle element, continue to search on the left
+ if the target value is larger, continue to search on the right

:::warning
The highly possible scenarios to use Binary Search:
+ ***Ordered*** array
+ No duplicates
:::


:pushpin:*Algorithm:*

Initialise left and right pointers : `left = 0`, `right = n - 1`
While `left <= right`:
&emsp; Compare middle element of the array `nums[pivot]` to the target value `target`
&emsp; &emsp; If the middle element is the target `target = nums[pivot]` : return `pivot`
&emsp; &emsp; Else continue the search on the right `left = pivot + 1`


:pushpin:*Time Complexity:*
+ O(logN)

:pushpin:*Consider the ==boundary conditions==:*

There are many boundary conditions involved, if you are not able to distinguish the boundary conditions, you will get error in determing `while(left < right)` vs `while(left <= right)`; `right = middle` vs `right = middle - 1`

+ Always follow :spiral_note_pad: [循环不变量原则](https://baike.baidu.com/item/%E5%BE%AA%E7%8E%AF%E4%B8%8D%E5%8F%98%E9%87%8F/8353186)

+ >The definition of an interval is an loop invariant. To maintain invariants during a binary search is to insist on operating according to the definition of an interval at every boundary processing in the while search, which is the loop invariant rule.
+ 2 ways to define interval:
+ `[left, right]`
+ `[left, right)`

***Chinese Version***

要对区间的定义理解清楚，在循环中要始终坚持**根据查找区间的定义**来做==边界处理==。

区间的定义就是不变量，那么在循环中坚持根据查找区间的定义来做边界处理，就是循环不变量规则。

不同边界所对应的code :point_down:

## Code

Python:

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums) - 1
        while left <= right:
            pivot = left + (right - left) // 2  #to avoid integer overflow issue that may caused by (left+right)/2
            if nums[pivot] == target:
                return pivot
            if target < nums[pivot]:
                right = pivot - 1
            else:
                left = pivot + 1
        return -1

Python(左闭右开区间)

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

## Questions

1. Is there any reason why we should focus on binary search over a recursive one?
Answer: 3 advantages of `Iterative` over `Recursive`:
- Recursion comes with **overhead** of saving current state. Hence, It's **slower**
- Recursion uses internal **Stack space**. So, **Space Complexity** of Recursive Approach is O(Log(n)) whereas Iterative is O(1)
- If the array length if very large, Recursive program can crash due to **Stack Overflow Error**