Prerequisites: Binary Search(Vanilla) , Find the First True in a Sorted Boolean Array
Thought Experiment
In the Question Binary search Vanilla to Chocolate. Instead of simply doing Binary Search, we combined Binary Search(Vanilla) and Find the First True in a Sorted Boolean Array . Reframing the problem to returning the first True value.
In this article, we will build on that by asking a question that will help us see the binary search in a different way and use it more flexibly. Does the array need to be sorted to run a binary search? Will a binary search work on an unsorted array?
nums = [1,2,3,4,6,5] with a target = 4
Yes, but how will binary search work if the array is not sorted? The sortedness is not the actual reason binary search works. What matters is that the elements in both halves of the array have the same property in how they relate to the value we are looking for, the target: greater than or less than the target, etc. In the example above, the positioning of 6 and 5 is irrelevant; all that matters is that they are on the right side of the target 4. #mindblown
_(1)/w=1920,quality=90,fit=scale-down)
/w=1920,quality=90,fit=scale-down)
Will we be able to solve this in logarithmic time target = 4?
You tell me!?
_(1)/w=3840,quality=90,fit=scale-down)
Yes.
Code and Execution for the problem above (Visualized)
Why is this relevant?
Understanding the location of the element relative to target gives us a better understanding of how binary search works, and will be our first insight into developing an intuition for solutions in logarithmic time. Will build on this principle in detail in First and last occurrence of an Element in a Sorted Array . So don’t forget to review that. Further, this will come full circle in Questions like,
Search in Rotated Sorted Array with Duplicates and Find a peak in a mountain array.. Although the given array may not be sorted, the questions possess all the necessary characteristics for applying Binary Search. Familiarizing ourselves with such questions will enhance our understanding of binary decisions in arrays and aid in solving Binary Search problems.