Thursday, October 11, 2012

Binary Search: First Occurrence of an Element

Problem: Find the first occurrence of an element in a sorted array.

Discussion: Binary search dictates that in order to find an element in a sorted array, we test the middle[1] element (call it pivot) for equality. If key is smaller than pivot, we search in subarray before pivot. If key is bigger, we search in subarray after the pivot. If equal, then we found the element. Divide an conquer.

This is a slight variant of it. We need to keep searching left until we ensure that it's the first occurrence.

Strategy: The first idea that comes to my mind, is to use regular binary search to find the element. It may not necessarily be the first occurrence. Now, we creep up the sorted array till we find an element less than the search key or we hit the boundary of the array. The complexity of this mechanism is O(log(n)) + O(k), where n is the array length, and k is repetition of key.

The other idea is to modify binary search slightly, and keep looking for the key in subarray preceding the 'pivot', if the pivot is equal to the `key` with element previous to the pivot is same as key and array boundary is not yet hit. This is O(logn). Here is the algorithm.
binary-first (A, key, low, high)
  if low > high
    return -1
    
  mid = low + (high - low)/2
  if key = A[mid]
    if mid > 1 and A[mid-1] == key
      return binary-first(A, key, low, mid-1)
    else
      return mid
  else if key < A[mid]
    return binary-first(A, key, low, mid-1)
  else
    return binary-first(A, key, mid+1, high)  
Footnotes:
[1] middle does not have to be mid. You may wish to use a random(low, high) as your pivot. However, mid as pivot makes it easy to think in terms of.

[2] View/download Java code at GitHub and sample execution here.

15 comments:

  1. كما تقدم الشركة شركة القائد عميلى العزيز اتصل بنا على شركة القائد وسوف نصلك اينما كنت نحن نهتم بالعميل جدا افضل شركة تنظيف بيوت بالدمام تنظيف منازل كبير يتم العامل بتنظيف الشقق باحدث المنظفات ويقوم بتنظيف الحوائط والارضيات على اكمل وجة لان  الشقه الكبيرة تحتاج الى عمال ممتازون وعمال جيدون فى مجال التنظيف ولزم الشقه الكبيرة تحتاج عمال كتير جدا لان الشقة الكبيرة تحتاج الى شركة القائد لان شركة القائد لديها عمال كتير جدا وهم يعملون فى شركتنا منذ سنوات كثيره جدا ويقوم بتنظيف المطابخ على اكمل وجه وتنظيف الشقق الصغيره عن طريق التنظيف بالمطهرات ويوجد لدين فى الشركة كل عامل لهو جوند يتم التنظيف بهاذا الجوند لاداعى للقلق شركة تنظيف بالدمام ويقوم المنظف بتنظيف الحمامات على اكمل وجة حيث ان عمالنا لديهم الخبرة فى تنظيف الحمامات الكبيرة ام الصغيرة ونحن افضل شركة تنظيف منازل بالدمام التنظيف هو عبارة عن تنظيف البيت كامل ويشمل جميع التنظيف شركتنا هى تعمل على تنظيف الفلل والشقق بالدمام عميلى العزيز اذا كنت تريد افضل شركة تنظيف منازل بالدمام اتصل بنا على افضل شركة فى الدمام اتصل بنا على افضل شركة تنظيف بالرياض ونحن نعمل داخل وخارج بجازان شركتنا تعمل فى جميغ انحاء المملكة العربية السعودية كما نقدم لكم خدمة التنظيف بجازان على اكمل وجة وفى الفترة الاخيرة تعد شركة القائد من افضل وارخص الشركات الموجودة فى جازان وفى الخبر ونحن نعمل فى الخبر وفى جازان وفى جميع انحاء المنطقة الشرقية شركة تنظيف بجازانعمال شركة القائد فى بالدمام يعملون على المكافحة باحدث الاجهزة الحديثة الموجودة فى شركة القائد نحن فى شركتنا لدينا جميع العمال الذين يعملون فى المكافحة والرش بالدمام هذه الشركة هى الشركة الممتازه فى الدمام اتصل بنا الان على افضل شركة مكافحة النمل الابيض بالدمام نحن نعمل فى ينبع منذ اكثر من سنوات كثيرة شركة مكافحة حشرات بالدمام عمال شركة القائد يعملون فى المكافحة منذ اكثر من اعوام كثيرة جدا اتصل الان نصلك عبر الهاتف المحمول عميلى العزيز انت تعلم ان شركة القائد هى الشركة الوحيدة التى تمتلك كبر عدد فى بجازان من الاجهزة الحديثة والمعدات الموجودة فى شركة القائد نحن نعمل فى جازان وفى جميع انحاء المملكة العربية السعودية تقدم شركة القائد افضل وارخص شركة مكافحة الفئران والصراصير بجازان كما تقدم شركة القائد افضل شركة مكافحة حشرات بجازان افضل الخدمات فى جازان منها شركة مكافحة حشرات بجازان ونحن فى جازان نعمل على مدار 24 ساعة يومين ولا نمل من مكافحة الحشرات لان الحشرات هى الوحيدة التى تسبب للاطفال امراض كثيره وكما تقدم شركة القائد خدمةشركة تسليك مجارى بالرياض نحن افضل شركة تسليك مجارى بالرياض اتصل بنا على افضل شركة فى الرياض لان شركة القائد من الشركات التى تمتلك الخبرة والكفائه العالة وهى التى تمتلك اكبر عدد من الاجهزة التى تستخدمها فى مجال تسليك المجارى بالرياض. تقدم الشركة افضل شركة نقل اثاث بجازان شركة القائد هى التى تعمل فى بجازان باحدث الاجهزة الحديثة الموجودة فى جازان اتصل بنا على افضل شركة نقل اثاث بجازان نحن الافضل فى جازان شركتنا من الشركات الموجوده فى جازان هى الشركة الوحيدة التى تمتلك اكبر عدد من السيارات لنقل الاثاث ونقل العفش بجازان اتصل بنا الان على افضل شركة نقل اثاث بجازان نصلك اينما كنت وفى اسرع وقت ممكن.

    ReplyDelete