binary search

Question

I/p - array of n element in which untill some postion all are integer and afterward all are star (*)

 

O/p- find the postion of 1st star (*)

Hint - if lenear search is possible the go to BS

Find time complexity ..?

Comments

If linear search is possible only then go to binary search?

And if linear search is not possible then go to?

---

If array is sorted then apply binary search it takes o(logn) time

---

if element is not sorted even then we can apply binary search here…..we apply binary search so that we can decide whether to go left or right in an array.

Answer 1

This problem can be solved by using Binary Search algorithm. Hence time complexity will be $ O(log n) $.

Strategies will be like this

1) Get the midpoint, and check the value at it

2) If the value is integer then directly move right

3) else if the value is a star then check whether it has integer at the immediate left position, if yes then print the location of the star, its the answer, else move to the left.

Comments

How can I get mid value
Without last postion of last element


Mid = I+j/2

But I don't know how to find "j"

---

If the array is infinite, that means we don’t have proper bounds to apply binary search. So in order to find position of key, first we find bounds and then apply binary search algorithm.
Let low be pointing to 1st element and high pointing to 2nd element of array, Now compare key with high index element,
->if it is greater than high index element then copy high index in low index and double the high index.
->if it is smaller, then apply binary search on high and low indices found.

---

the size $n$ is given in the question. isn't it?

---

Given array is of n elements. By using given information you can find UB

Answer 2

Linear search is possible.

To solve it from binary search

1. It is the same case when we are applying binary search for an absent element in a sorted array.

2. Here difference is we have to search a *.

3. Solve it by recursion. Find the mid point by low+high/2. If mid point = any number then make low=mid point. And if mid point= * then make high=mid point.

Function (low,high,array[ ])

T(n)=T(n/2)+1

4. In ever recursion check if(high=low+1) then index of first * is index of high.

Complexity O(logn)

Answer 3

(logn).... We can search it by binary search tree ... First it goes in multiples of 2 and checks its left and right values...