Introduction

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.

1
2
3

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

1
2
3

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

Process

This is a normal binary search, splitting each search iteration by $\frac{1}{2}$, I created a new function with left and right variables to indicate the high and low pointers on the array.

Since the array is already sorted in ascending order, the larger numbers will always be to the right of the mid value.
The mid index value could be found using the floor division of left + right:

1

mid = (left + right) // 2

though I realise that using a right shift would make it faster

1

mid = (left + right) >> 1

After getting the midpoint, there will be 3 conditions left:

1. nums[mid] == target
2. nums[mid] < target
3. nums[mid] > target

For each of this conditions, I’ll update the pointers or return the mid value. this is all done in a while loop where left needs to be $\le$right and left should not go past right (Value Not Found).

At the end, I’ll return -1 if the value isn’t found.

Calling the function in the return statement of the outer function definition, I’ll pass 0 and len(nums) -1 into the binary search function.

This solution takes a Time Complexity of $O(\log n)$ and Space Complexity of $O(1)$ as it only requires the size of the array.

Solution

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

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

                else:
                    left = mid + 1
            return -1

        return bSearch(0, len(nums)-1)

Afterthoughts

This is my first step into revising for my Data Structures and Algorithms. Binary search is one of the fastest searching algorithms, with $O(\log n)$ Time Complexity. Coupled with a fast Sorting algorithm, Users will be able to sort and search for values quickly and efficiently.