CODEWITHSUNDEEP
c++algorithmdata-structurestime-complexity
Vivek Singh
Vivek Singh

Reputation: 114

Searching the element in array with complexity better than O(n)

I have any array where the elements are first in increasing order and then in a decreasing order

Like A[10]={1,4,6,8,3,2} , with no duplicates in an array.

if the input is 7, Output should be, Element do not exist.

Time complexity should b better thn O(n)

I am getting the result by the linear search, comparng each elemnts with the element to b found. But as I want solution better then O(n)

I tried by finding a pivot where the array element flips, and then searching from (0 to pivotelement) and then again searchiing in (last elemnt to pivot elemnt).

Please suggest. For O(n)

 #include<iostream>
 int main()
 {
     int A[10]={1,4,6,8,3,2};
     int i,num
     cout<<"Enter the element to be searched";
     cin>>num
     for(i=0;i<10;i++)
     {
         If(A[i]==num)
        {
          cout<<"Element exist";
         break;
      }
         else
         cout<<"Element do not exist";
     }
 }

Upvotes: 2

Views: 1474

Answers (1)

Tony Tannous
Tony Tannous

Reputation: 14876

Algorithm:

  1. Find max in log(n) by doing a binary search and save its index.
  2. Do a binary search on the two sides of max.
  3. If not found and the element doesn't equal the max, then it doesn't exist.

How to do step 1 ?

  • pick the middle of the array
  • check it against the item on the left (your neighbour). If greater, then max is on the right side. Otherwise, we started in the decreasing sequence and max is on the left side. The way to choose wether to search on the right/left depends if the item on the left is greater/smaller.

EDIT
Just in case it was not clear: if you pick n/2-th element and turns out max is on the left, then you pick n/4-th element, if the max is on its right side, you only continue the search in the range n/4...n/2 elements.

Upvotes: 5

Related Questions