704. Binary Search

### Description#

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.

### Solution#

Prerequisites for using binary search:

• Ordered list
• All elements are unique (if not, the value returns probably is not unique)

For binary search method, one important thing is to clearly define interval’s close and open situation. Usually we have two kinds of intervals:

• Left close and right close [left, right]
• Left close and right open [left, right)

#### For left close and right close [left, right]#

Two points:

• while (left <= right) should use <=, because it’s meaningful ween left == right since we use [left, right]
• if (nums[middle] > target) right we need to let nums[middle] = - 1，because we are sure nums[middle] is not our target，so the ending condition is when we come across element with index is -1
class Solution:
def search(self, nums: List[int], target: int) -> int:
left, right = 0, len(nums) - 1

while left <= right:
middle = (left + right) // 2  #Floor Division

if nums[middle] < target:
left = middle + 1
elif nums[middle] > target:
right = middle - 1
else:
return middle
return -1


#### For left close and right open [left, right)#

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