<aside> 😀 Click here for the LeetCode link.

</aside>

📝 Solution

1. Boundary check!
   1. the length of the array is 1, and then we just need to check if the only element is the target.
   2. check if the last element in the array is the target.
2. Define three pointers, left: l; middle: m; right: r. For a given subarray, l is the index of the first element in the subarray, r is the index of the last one, and m is the floor division of l + r by 2.
3. The loop condition is l < m < r, i.e. l + 1 < r. That is, the subarray needs to at least keep the form [nums[l], nums[m], nums[r]]; otherwise, break the loop.
4. Within the loop,
   1. check if nums[m] is the target. If yes, return m; if no, divide the array.
   2. after partitioning the array into 2 subarrays, we have two disjoint subarrays, [nums[l], nums[m - 1]], and [nums[m], nums[r]].
   3. update l, m and r. For example, if we need to keep the second subarray, then r does not need any changes. Update l to the current m and recalculate m by (l + r) // 2.
   4. Check boundaries if the target is there.

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        n = len(nums)
        if n == 1:
            if target == nums[0]:
                return 0
            else:
                return -1

        if target == nums[0]:
            return 0
        if target == nums[-1]:
            return n - 1

        l, r = 0, n - 1
        m = (l + r) // 2

        while r - l > 1:
            if target == nums[m]:
                return m

            if target > nums[m]:
                l = m
            elif target < nums[m]:
                r = m - 1 
            
            m = (l + r) // 2

            if target == nums[l]:
                return l
            if target == nums[r]:
                return r
            
        return -1

<aside> 💡 Leave me a comment for a further discussion!

</aside>