Imagine array as people line up and facing a wall, whenever a person want to join the queue, we can either choose a person, push him back and sit in front of him, or join at the end of the queue. The natural of array list cause that, we are searching right (I am bigger than you, then I join behind you so i + 1), if we are searching left (I am smaller than you, I don't have to move but push you behind as i). That is why we can always choose the lower bound pointer. At first I am thinking why god create left and right bound unequally.
Approach The problem is little bit modified when compared to finding the floor/ceil of an element using binary search. Usually to find the floor,(Here I am assuming you know the basic binary search concept of finding the floor and ceil) we consider the rightmost search space. if(nums[mid]
left and right pointers define the range in which the target lies. so if left is 3 and right is 12 then the target could be at any index from 3 to 12 including 3 and 12. now imagine what happens when left = right = some number, say 4 then the target could be at any index from 4 to 4 including 4. see it? it means it must be at 4(=left = right).
I am also confused with it. What I understand is that it depends on how you move your boundary. If you don't set the boundary over the mid (e.g left = mid, but not left = mid+1), you should be careful about using
one of the things I noticed when solving this problem is that if the target is less than nums[0] you should return 0, and if the target is greater than nums[len(nums)-1], to return len(nums). do you think this is efficient or just a waste of space/time?
@@ravivanam7868ardon me if this is a dumb question but how would the code still work if the target is out of bounds, won't the program stop executing after it returns 0?
for a moment i was feeling really dumb, i tried different ways and stuck for about 45 mins, then i saw ur explaination,, i wonder why this logic didn;t hit me ,, im feeling really dumb😓😓
we are updating the range to search here.. if the target is not equal to element at position mid, we can say that it has to lie either on left or right side of mid ,i.e search area will half of the previous. if target is less than mid then we search on left side with right=mid-1 ( we are not considering element at mid because we already checked if target== element at mid) and the other case left=mid+1 if target> element at mid.
@@Saotsu1 on leetcode it says that the runtime is 102 ms and it beat about 46 percent of submissions. It that slow? I heard that leetcode sometimes give random numbers about submissions
Not me patching up six conditions like the transformers in Transformers 2 that joined together to barely crawl pass through the finish line and guy just does a regular binary search QAQ
Cool solution. I only looked at this once i finished my solution. Mine was basically implement binary search, and if it doesnt work, there are 3 cases to take account for. Code: begin = 0 end = len(nums) - 1 last_value = len(nums) - 1 first_index = 0 while begin target: end = midpoint - 1 else: return midpoint for i in range(len(nums)): if target > nums[last_value]: return last_value + 1 if target < nums[first_index]: return 0 if nums[i] < target < nums[i+1]: return i+ 1
i would have never come out with this lol. Maybe, i would have studied computer science and all i did was code and learn a gang of techniques and thrive to always come out with new ways to make algorithms ran faster and more efficient...crazy, respect to you mah software engineeris, programmers or whatever you are. honestly , im happy with iteration throught the entire loop lol Doesn't that make more sense haha. jk, ima memorize this technique like people memorize Maradona and Magico Gonzales tricks and then show the world
