during solving binary search questions I came across two questions In which there is the utilization of condition " while start <= end: " differently which make me understand the value of = in this type of question
1 st question -->
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
def binarySearch(nums, target):
left = 0 right = len(nums) - 1
while left <= right: mid = (left + right) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
2nd question in which = not need
Peak Index in a Mountain Array
An array arr
a mountain if the following properties hold:
arr.length >= 3
There exists some
i
with0 < i < arr.length - 1
such that:arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
arr[i] > arr[i + 1] > ... > arr[arr.length - 1]
Given a mountain array arr
, return the index i
such that arr[0] < arr[1] < ... < arr[i - 1] < arr[i] > arr[i + 1] > ... > arr[arr.length - 1]
.
You must solve it in O(log(arr.length))
time complex
solution
class Mountain:
def peakIndexInMountainArray(self, arr):
start = 0 end = len(arr) - 1
while start < end:
mid = start + (end - start) // 2
if arr[mid] > arr[mid+1]:
end = mid
else:
start = mid + 1
return start
so what change happens with a simple ''=''
If you change the while loop condition from "while start < end" to "while start <= end", it will cause the function to return an incorrect result in some cases.
When the start pointer becomes equal to the end pointer, it means that the search space has been narrowed down to one element, which should be the peak element. In this case, the loop should exit and return the value of the start pointer. However, if you use the "while start <= end" condition, the loop will continue to execute even after the start pointer becomes equal to the end pointer. In this case, the function will return an incorrect result.
For example, if the input array is [1,2,3,4,3,2,1], the correct output should be 3 (the index of the peak element), but if you use "while start <= end" condition, the function will return 4 (which is an incorrect result).
So, it is important to use the correct loop condition "while start < end" in this specific problem to get the correct output.