Search

1. Search One Element in Sorted Array (when we know the element)

   1. Binary Search

   2. Example questions:

      1. 852_ Peak Index in a Mountain Array

2. Search One element in an Array (When we don't know the element, but know it's property, ie. kth largest, median)

   1. Use the idea of quick sort

   2. Example questions:

      1. 215_Kth Largest Element in an Array

3. Search Two Elements in Sorted Array

   1. Two passes of binary search

      1. Example questions:

         1. 34_Find First and Last Position of Element in Sorted Array

   2. Two pointer

4. Search in Rotated Sorted Array

   1. Binary search. Identify the part that is not rotated by comparing the values on the left and right.

   2. Example questions:

      1. 33_Search in Rotated Sorted Array

      2. 153_Find Minimum in Rotated Sorted Array

5. Search for more than two elements

   1. convert to search for two elements

6. Search in Unsorted Array

   1. we can sort first

   2. usually use dictionary to keep corresponding information

7. Use Math Properties

   1. Use the property of sum, average, etc.

   2. Example questions:

      1. 268_Missing Number

8. Bit Manipulation

Notes for search:

1. Sorted array with distinct elements or with duplicates could make a huge difference in search algorithm. Many times if all elements are distinct, we can find algorithm in $O(\log{n})$ such as binary search. If duplicates exists, it may be hard to avoid $O(n)$ algorithm.

Binary Search Template

# return the location of number t in sorted array A, if not, return -1.
def bsearch(t, A):
    L, R = 0, len(A)-1
    while L <= R:
        M = L + (R-L)//2
        if A[M] == t:
            return M
        elif A[M] < t:
            L = M + 1
        else:
            R = M - 1
    return -1

For assigning new M, use M = L + (R-L)//2 instead of M = (L + R)//2 to avoid overflow. The overflow may happen if L and R are larger than the largest possible integers in the system. Refer to this post for details.

Reminder:

1. Sometimes when we use binary search, we don't need to test the equal sign. We can jus throw away the left part or right part. In this case, we will update index as L = M or R = M.