Binary Search I

Basic Scenario

Find the index of a target matching element in a sorted (either ascending or non-increasing) array.

Classic examples

lc 704 Search target

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 <= 104
-104 < nums[i], target < 104
All the integers in nums are unique.
nums is sorted in ascending order.

def binarySearch(nums,target):
    l,r = 0, len(nums)-1
    while l <= r: #*
        mid = (l+r)//2
        if target < nums[mid]:
            r = mid - 1 #*
        elif target > nums[mid]:
            l = mid + 1 #*
        else:
            return mid
    return -1

lc 35 Insert target
search ends at l = r+1, so finally return l if not found (or r+1).

def searchInsert(nums,target):
    l,r = 0, len(nums)-1
    while l<=r:
        mid = (l+r)//2
        if nums[mid]< target:
            l = mid+1
        elif nums[mid] > target:
            r = mid-1
        else:
            return mid
    return l #*

Summary:

1. Both arrays are in an ascending order (no duplicates).
2. There are usually two representations for intervals: [left, right] and [left, right). I prefer the former, so all the binary search code in blogs is based on the [left, right] format.

Next blog: How to find left and right borders of target in a non-inscreading array. How to search target in unsual array.