I learned more than Binary Search in my first meetup!

After two weeks at a data science immersive bootcamp, I visited my first meetup “Women Who Code in DC”. We were presented with the following challenge, which was taken from leetcode.
Challenge:
Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order. You may assume no duplicates in the array.
Example 1:
Input: [1, 3, 5, 6], 5
Output: 2
Example 2:
Input: [1, 3, 5, 6], 2
Output: 1
Example 3:
Input: [1, 3, 5, 6], 7
Output 4
Example 4:
Input: [1, 3, 5, 6], 0
Output: 0
My solution: I solved this challenge applying an if and else statement that allowed me to identify the index of the target in the array. However, my function was not efficient since it was iterating over and over again along every number of the array. When the best solution was shared, I learned about the binary search approach and how it can make your algorithm more efficient.
class Solution(object):def searchInsert(self, nums, target): if target in nums: return nums.index(target) else: nums.append(target) nums.sort() return nums.index(target)""":type nums: List[int]:type target: int:rtype: int"""
Introducing the Binary Search Approach:
A binary search is an approach that allows you to search along a sorted array by repeatedly dividing the search interval in half. If the value you are searching is less than the value located in the middle of the interval, the search process will focus only on the lower half. Otherwise the search will continue on the upper half.
Example: Searching for value 12 on the following array.
Array: [1, 4, 6, 7, 9, 12, 14, 13, 15, 19]
The middle point is 9. We know that 9 is lower than 12. Therefore focus your search on the upper half.
Array: [1, 4, 6, 7, 9, 12, 13, 14, 15, 19]
The middle point of the upper half is 14. 12 is lower than 14. Therefore focus your search on the lower half.
Array: [1, 4, 6, 7, 9, 12, 13, 14, 15, 19]
Found 12. Return the index 5 for its position.
Array: [1, 4, 6, 7, 9, 12, 13, 14, 15, 19]
The main benefit of this approach is that it reduces the complexity and the time to run the algorithm.
The solution to the challenge: This solution was posted by Marina Sergeeva at the slack channel of Women Who Code from Washington D.C.
class Solution:
def searchInsert(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
left = 0
right = len(nums)
return self.binary_search(nums, target, left, right)
#Returns index of target in array nums
def binary_search(self, nums, target, left, right):
if right - left <= 1:
if nums[left] >= target:
return left
else:
return left + 1
med = (left + right) // 2
# If element is present at the middle itself
if nums[med] == target:
return med
# If element is larger than med, then it
# can only be present in right subarray
if nums[med] > target:
return self.binary_search(nums, target, left, med)
# Else the element can only be present
# in left subarray
else:
return self.binary_search(nums, target, med, right)Main takeaways:
- Meetups are a great way to practice what you have learnt so far. Even if what you know is not enough to solve the meetup coding challenges, you will learn how to approach them by the end of the session.
- If you are a coding beginner, expose yourself to the community of coders in your city. You can learn from them and get unique insights of things that matter in real situations outside of a class.
- As a woman, it was great to see more women coders in action.
- When you design your algorithm, think about ways in which you can reduce its complexity and increase its efficiency.
Sources:
https://www.geeksforgeeks.org/binary-search/
https://leetcode.com/problems/search-insert-position/description/