-1

for example if list= [2,3,3,4,5,7,7,9,10],

i want to return index 1.

In this case,there is no target parameter unlike the usual way we do binary search

[Updated]

[This is the code that I have for now.It should return 1 since the first occurence of a multiple value,which is 2,is at index 1

Link for photo of code

[Updated]

Low Wijjy
  • 1
  • 1
  • Does this answer your question? [Finding the index of an item in a list](https://stackoverflow.com/questions/176918/finding-the-index-of-an-item-in-a-list) – RoadRunner May 13 '20 at 10:42
  • What code have you tried, and what isn't working? Please try to research and attempt before you ask. – Run_Script May 13 '20 at 11:54
  • you can refer to my updated description for more details about my problem – Low Wijjy May 13 '20 at 14:45

2 Answers2

0

Perform your binary search as usual; but when you arrive at the item you searched for, keep searching to the left.

I.e.:

  • Set min to the first index, max to the last (plus one).
  • Look at the one in the middle ((min+max)/2).
  • If the value there is larger than the one you are searching for, set max to that index; else that min to it (plus one).
  • Repeat until you find an index with the value you are looking for.
  • So far this was just the regular binary search. Now store that index; it is your current best candidate. Act like the value you found was larger than what you were looking for (i.e., set max to that index), and continue with the search.

When you run out of search space (i.e., min = max), the last "candidate" you found is the lowest index of the value you searched for.

AnoE
  • 8,048
  • 1
  • 21
  • 36
  • in regards to your third point,i do not have a preset value at the start to search for.My function must not require that and yet be able to find the first occurence of a multiple value and return its index. – Low Wijjy May 13 '20 at 14:38
  • @LowWijjy: I see; I'd suggest to add that more explicitly to the question to increase the chance for someone to come up with a good idea. As you see, both my algorith and bhaskar's implementation of it do not really "understand" it correctly... – AnoE May 14 '20 at 13:09
-1

i am sharing you code snippet which will help to find your answer 

int leftIndex(int arr[], int n, int x)
{
    int l = 0, h = n-1;
    int mid = 0;

    while(l <= h)
    {
        mid = l + (h-l)/2;

        if(arr[mid] == x && (mid == 0 || arr[mid-1] != x))
          return mid;

        else if(arr[mid] >= x)
          h = mid-1;
        else l = mid + 1;
    }
    return -1;
}

You just need to understand this code . this is as simple as binary search code. just a single condition where we need to modify the so that we can get required result

bhaskar shelar
  • 28
  • 7
  • your x variable in this case is the target parameter that i dont require in my example of binary search.My binary search function would not have a target parameter to search of,no preset value to be found – Low Wijjy May 13 '20 at 14:25
  • Hi there .. we use binary search to find respective value . we can't use binary search f we don't know what to find . but i worked on your problem to find the required anwer in O(1) time complexity .. int arr[]={2,3,6,9,11,12,12,19,20}; int n=9; unordered_set us; for(int i=0;i – bhaskar shelar May 13 '20 at 15:13