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.

19 comments:

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

    ReplyDelete
  2. شركة تسليك مجارى بالدمام شركة ركن الامثل 0502644550

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

    ReplyDelete
  3. خدمات شركة ركن الامثل لتسليك المجارى بالقطيف 0502644550



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

    ReplyDelete
  4. شركة تسليك مجارى بالجبيل 0502644550 شركة ركن الامثل

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

    شركة مكافحة حشرات بالجبيل
    شركة تنظيف منازل بالجبيل
    شركة رش مبيدات بالجبيل
    شركة كشف تسربات المياه بالجبيل
    شركة تنظيف سجاد بالجبيل
    شركة تنظيف شقق بالجبيل
    شركة تنظيف فلل بالجبيل
    شركة تنظيف كنب بالجبيل
    شركة تنظيف مجالس بالجبيل

    ReplyDelete